Dijkstra最短路径算法实习报告

通过Dijkstra最短路径算法,解决有向图即交通网络模型中源点到其他顶点的最短路径问题,VC编程实现。

Dijkstra最短路径算法实习报告

1.引言

交通诱导系统的一个核心技术是最优路径的选择技术。根据交通网络模型中各顶点和顶点之间的长度、时间或费用等属性权值，通过Dijkstra最短路径算法，解决有向图即交通网络模型中源点到其他顶点的最短路径问题。

2.建立交通道路网络模型

交通道路网是路径诱导的基础和对象，首先需要建立交通道路网络模型。交通道路网中的路段具有属性，且同一路段的两个方向其属性一般不完全相同，有向图能够很好地表达实际的交通网络，便于处理同路段两个方向的不同属性和单行线、交叉口转向限制等特殊交通属性。综上，采用带权有向图来表达交通道路网。其中，道路的终点和十字路口通常定义为一个顶点，两个顶点之间的道路定义为一条弧，每条弧根据其距离、途中所需时间或交通费用等定义为路段权值。在有向图上，一条以i为起点，以j为终点的路径是一些顶点的序列，其中前一条弧的终点是后一条弧的起点，一条路线用一个有序的点集描述，而一条路线的长度、时间或者费用等属性为这条路径上的所有弧的权值之和。这样便建立好了交通道路网络的模型。

3.最短路径算法

迪杰斯特拉（Dijkstra）算法是经典路径诱导规划算法，Dijkstra算法是一个按路径长度递增的次序产生最短路径的算法，算法比较简单，容易实现，但计算量较大。

3.1算法分析：首先引进辅助向量D，它的每个分量D[i]表示当前所找到的从始点v0到每个终点vi的最短路径的长度。为D[i]赋初值，若从v0到vi有弧，则D[i]为弧上的权值，否则置D[i]为∞。则长度为D[j]=Min{D[i]|vi∈v}的路径就是从v0出发的长度最短的一条最短路径，此路径为v0—vj。设下一条长度次短的路径的终点是vk，则这条路径或者是v0—vk，或者是v0—vj—vk。它的长度是v0到vk弧上的权值或D[j]和vj到vk弧上权值之和。

3.2算法正确性证明：设s为为已切得最短路径的终点的集合，则有结论：下一条最短路径（设其终点为vx）或者是v0—vx，或者是中间只经过s中的顶点而最后到达顶点x的路径。采用反证法证明如下：假设此路径上有一个顶点 不在s中，则说明存在一条终点不在s而长度比此路径短的路径。这是不可能的，因为Dijkstra算法是按路径长度递增的次序来产生各最短路径的，弧长度比此路径短的所有路径均已产生，它们的终点必定在是中，故假设不成立，算法正确可行。

3.3算法描述：

设起始点为v0，顶点集为v，初始态vi∈v。

（1）用带权邻接矩阵arcs表示带权有向图，arcs[i][j]表示弧<vi，vj>上的权值。若<vi，vj>不存在，则置arcs[i][j]为∞。S为已找到从v0出发的

通过Dijkstra最短路径算法,解决有向图即交通网络模型中源点到其他顶点的最短路径问题,VC编程实现。

最短路径的终点的集合，它的初始状态为空集。从v0出发到图上其余各顶点（终点）vi可能达到的最短路径长度的初值为：D[i]=arcs[0][i] vi∈v。

（2）选择vj，使得D[j]=Min{D[i]|vi∈v-s}，vj就是当前求得的一条从v出发的最短路径的终点，并令s=s∪{j}。

（3）修改从v0出发到集合v-s上任一顶点vk可达的最短路径长度。如果D[j]+arcs[j][k]<D[k],则修改D[k]为D[k]=D[j]+arcs[j][k]。

（4）重复操作（2）、（3）共n-1次，由此求得从v0到图上其余各顶点的最短路径是一次路径长度递增的序列。

3.4Dijkstra 算法的执行速度：Dijkstra 算法的最初的时间复杂度为O（V*V+E），源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV），当是稀疏图的情况时，E=V*V/lgV，算法的时间复杂度可为O（V^2）。用大O符号将Dijkstra 算法的运行时间表示为边数 m 和顶点数 n 的函数。Dijkstra 算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合 Q，所以搜索 Q 中最小元素的运算（Extract-Min(Q)）只需要线性搜索 Q 中的所有元素，这样算法的运行时间是 O(E^2)。

3.5Dijkstra算法实现：定义n为有向图中的顶点个数，arcs[i][j].w为有向图中顶点i到顶点j的权值。首先利用如下语句为邻接矩阵赋初值，均为∞。

有向图中，若vx到vy有弧利用下面语句依次输入顶点号和弧上权值，并将权值赋给arcs[vx][vy].w。至此，交通网路模型即带全有向图建立完成。

输入出发顶点v0 ，置已找到从v0出发的最短路径的终点的集合s[n]初始状态为空集。通过以下语句找到从v0出发的最短路径的终点vj，使得

D[j]=Min{D[i]|vi∈v-s}

上述语句中的条件语句if（find(s,i)!=1）是确保顶点vi在v-s中，find(s,i)函数的作用是若顶点vi在s中返回1，否则返回0。其代码如下：

通过Dijkstra最短路径算法,解决有向图即交通网络模型中源点到其他顶点的最短路径问题,VC编程实现。

接下来需要对已写入的最短路径长度做修改，利用下面的语句完成如果

D[j]+arcs[j][k]<D[k],则修改D[k]为D[k]=D[j]+arcs[j][k]，并利用before[j]记录vj顶点的前一个顶点，用以输出路径的顶点序列。语句最后的s[k++]=v是将已经求得终点放入集合s中。若有修改则v0到vj的路径中间有若干顶点，若无修改则v0到vj的最短路径就是v0—vj。

最后同过输出语句输出起始点v0到各个顶点的最短路径的权值和路径的顶点序列。若arcs[v0][i].w =INFINITY，则表示v0到vi无穷远，无法到达。

3.6算法实现：结合实例展示成果。

下图为一个带权有向图：

通过Dijkstra最短路径算法,解决有向图即交通网络模型中源点到其他顶点的最短路径问题,VC编程实现。

下图显示该有向图中从v0到其余各点的最短路径：

程序执行结果：

输出结果与预期结果相同，正确地实现了Dijkstra最短路径算法。

参考文献

严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，1997.186-190. 徐士良.实用数据结构[M].北京：清华大学出版社，2007.133-139.

底园园，苏小会.交通诱导系统中动态路径诱导算法的研究[j].计算机与数字工程，2011,39（2）：33-35.

鲍培明.距离寻优中Dijkstra算法的优化[j].计算机研究与发展，2001,38

（3）：

307-309.