dijkstra算法 dijkstra算法求解最短路径例题( 二 ) _生活百科

15、再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时vi到vj的边，如果不存在边则为空。
16、执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点vi到终点vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。
17、接着把vm并入集合S中，然后以vm作为新考虑的中间顶点，对S以外的每个顶点vj，比较dist[m]+GA[i，j]与dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把vj或边（vm，vj）并入到path[j]中。
18、重复以上过程n-2次，即可在dist数组中得到从源点到其余个终点的最短路径长度，对应的path数组中保存着相应的最短路径。
19、为了实现上的方便，用一个一维数组s[1..n]代替集合s，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点vj不在集合中，反之，s[j]表示顶点vj已在集合中）。
20、Procedure dijkstra (GA,dist path,I) beginfor j:= 1 to n do beginif j<>I then s[j]:=0;{j不在集合中}else s[j]:=1;{j在集合中}；dist[j]:=GA[I,J];IF dist [j]I then s[m]:=1else exit;{若条件成立，则把Vm加入到s中，否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去} for j:=1 to n do {对s[j]=0的更优元素作必要修改}if (s[j]=0)and (dist[m]+GA[m,j] 本文到此分享完毕，希望对大家有所帮助。