dijkstra算法求最短路径.doc

在交通网络中,常常会提出许多这样的问题:两地之间是否有路相通?在有多条通路的情况下,哪一条最近?哪一条花费最少等。交通网络可以用带权图表示,图中顶点表示域镇,边表示两城之间的道路,边上权值可表示两城镇间的距离,交通费用或途中所需的时间等。以上提出的问题就是带权图中求最短路径的问题,即求两个顶点间长度最短的路径。最短路径问题的提法很多。在这里仅讨论单源最短路径问题: 即已知有向图( 带权), 我们希望找出从某个源点 S∈V到G 中其余各顶点的最短路径。例如:下图( 有向图 G 14) ,假定以 v 1 为源点,则其它各顶点的最短路径如下表所示: 图 G14 从有向图可看出, 顶点 v 1到v 4 的路径有 3条: (v 1 ,v 2 ,v 4), (v 1 ,v 4), (v 1 ,v 3 ,v 2 ,v 4), 其路径长度分别为: 15,20 和 10 。因此 v 1到v 4 的最短路径为(v 1 ,v 3 ,v 2 ,v 4)。为了叙述方便,我们把路径上的开始点称为源点,路径的最后一个顶点为终点。那么,如何求得给定有向图的单源最短路径呢?迪杰斯特拉(Dijkstra) 提出按路径长度递增产生诸顶点的最短路径算法,称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是:设有向图 G=(V,E) ,其中, V={ 0 ,2,…,n -1}, cost 是表示 G 的邻接矩阵, [i][j] .adj 表示有向边<i,j> 的权。若不存在有向边<i,j> ,则 [i][j] .ad j 的权为无穷大( 这里取值为 32767) 。设S 是一个集合, 其中的每个元素表示一个顶点, 从源点到这些顶点的最短距离已经求出。设顶点 v0 为源点,集合 S 的初态只包含顶点 v 0 。数组 D 记录从源点到其他各顶点当前的最短距离, 其初值为 D[i]= [v0][ i ].adj , i=1,…,n -1。从S 之外的顶点集合 V-S 中选出一个顶点 w ,使 D[w] 的值最小。于是从源点到达 w 只通过 S 中的顶点,把 w 加入集合 S中调整 D 中记录的从源点到 V-S 中每个顶点 v 的距离: 从原来的 D[v] 和 D[w]+ [w][v] .adj 中选择较小的值作为新的 D[v] 。重复上述过程,直到 S 中包含 V 中其余顶点的最短路径。最终结果是:S 记录了从源点到该顶点存在最短路径的顶点集合, 数组 D 记录了从源点到 V中其余各顶点之间的最短路径, P 是最短路径的路径数组,其中 P [i] 表示从源点到顶点 i 之间的最短路径的前驱顶点。// 定义状态代码及数据类型#define NULL 0#define OK 1#define ERROR 0 #define TRUE 1#define FALSE 0 #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef int Status; // ---------------------- 图的结构:邻接矩阵--------------------------// // 邻接矩阵元素· typedef struct ell{ int adj; // arc value: >0,