Dijkstra算法求最短路径.doc

在交通网络中，常常会提出许多这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最近？哪一条花费最少等。交通网络可以用带权图表示，图中顶点表示域镇，边表示两城之间的道路，边上权值可表示两城镇间的距离，交通费用或途中所需的时间等。　在交通网络中，常常会提出许多这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最近？哪一条花费最少等。交通网络可以用带权图表示，图中顶点表示域镇，边表示两城之间的道路，边上权值可表示两城镇间的距离，交通费用或途中所需的时间等。　　以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径。　　最短路径问题的提法很多。在这里仅讨论单源最短路径问题：即已知有向图(带权)，我们希望找出从某个源点S∈V到G中其余各顶点的最短路径。　　例如：下图(有向图G14)，假定以v1为源点，则其它各顶点的最短路径如下表所示：图 G14　　从有向图可看出，顶点v1到v4的路径有3条：(v1,v2,v4)，(v1,v4)，(v1,v3,v2,v4 )，其路径长度分别为：15,20和10。因此v1到v4的最短路径为(v1,v3,v2,v4 )。　　为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。　　那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉(Dijkstra)提出按路径长度递增产生诸顶点的最短路径算法，称之为迪杰斯特拉算法。　　迪杰斯特拉算法求最短路径的实现思想是：设有向图G=(V,E)，其中，V={0,2,…,n-1}，cost是表示G的邻接矩阵， [i][j].adj 表示有向边<i,j>的权。若不存在有向边<i,j>， [i][j].adj的权为无穷大(这里取值为32767)。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v0为源点，集合S的初态只包含顶点v0。数组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 ArcC