5.6 最短路径★3◎4

5.6 最短路径★3◎4　　在带权图中，一条路径上各边的权值总和称为“路径长度”，两个顶点间长度最

作者

次阅读

2010-11-16

5.6 最短路径★3◎4

　　在带权图中，一条路径上各边的权值总和称为“路径长度”，两个顶点间长度最短的路径称为“最短路径”。
　　最短路径问题在实际中应用很广泛，比如交通网络：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，求两个城镇之间的最短距离就是带权图中两个顶点之间的最短路径。
　　在带权图中，习惯上我们称路径开始的顶点为“源点”，路径的最后一个顶点为“终点”。
　　1．求单个顶点到其他顶点的最短路径
　　（1）问题提出
　　已知有向带权图（简称有向网）G=(V, E)，找出从某个源点s∈V到V中其余各顶点的最短路径。
　　（2）迪杰斯特拉（Dijkstra）算法基本思想
　　设S为最短距离已确定的顶点集，则V-S是最短距离尚未确定的顶点集，增加一个辅助向量D，它的每个分量D[i]表示当前已知的从源点s到终点Vi的最短路径长度。
　　①算法开始时，只有源点s的最短距离是已知的(D[s]=0)，此时已确定顶点集S={s}，同时向量D的每个分量取值可以从邻接矩阵A中获得。
　　②针对每一个Vi∈V-S，重新计算源点S到终点Vi的最短路径长度D[i]，计算方法如下：
　　假设新加入集合S的顶点为Vj，如果D[j]+A[j,i]<D[i]，则将D[i]赋值为D[j]+A[j,i]，并记下此路径。
　　③在集合V-S的所有顶点中，选取一个距离S点路径长度最短的，将此顶点加入集合S中。
　　④重复执行步骤②和③，直到集合V-S为空，或者集合V-S中所有顶点距离S的路径长度为无穷大时结束。
　　（3）算法实例
　　用迪杰斯特拉算法求图5-12(a)的顶点V0到其他顶点的最短路径长度。

　　初始时S为{V0}，D[0]=0，其余步骤如表5-7所示。

表5-7 迪杰斯特拉算法求V0到其他顶点最短路径步骤

集合 S	向量 D					分析
V0	V1	V2	V3	V4	V5
V0	∞	10	∞	30	100	集合V-S中顶点V2对应数值最小，所以V2入S
V0,V2	∞	10	60	30	100	①集合V-S中顶点V4对应数值最小，所以V4入S
V0,V2,V4	∞	10	50	30	90	②集合V-S中顶点V3对应数值最小，所以V3入S
V0,V2,V4,V3	∞	10	50	30	60	③集合V-S中顶点V5对应数值最小，所以V5入S
V0,V2,V4,V3,V5	∞	10	50	30	60	集合V-S中顶点到S的最短路径长度均为∞，算法结束，向量D即为所求。

　　分析：
　　① S集合中新加入顶点V2
　　顶点V1
　　分析V2：A[2,1]为∞，D[1]取值不变
　　顶点V3：
　　分析V2：D[2]+A[2,3]=10+50=60 < D[3]=∞，所以D[3]=60
　　顶点V4：
　　分析V2：A[2,4]为∞，D[4]取值不变
　　顶点V5：
　　分析V2：A[2,5]为∞，D[4]取值不变
　　② S集合中新加入顶点V4
　　顶点V1：
　　分析V4：A[4,1]为∞，D[1]取值不变
　　顶点V3：
　　分析V4：D[4]+A[4,3]=30+20=50 < D[3]=60；所以D[3]=50
　　顶点V5：
　　分析V4：D[4]+A[4,5]=30+60=90 < D[5]=100；所以D[5]=90
　　③ S集合中新加入顶点V3
　　顶点V1：
　　分析V3：A[3,1]为∞，D[1]取值不变
　　顶点V5：
　　分析V3：D[3]+A[3,5]=50+10=60 < D[5]=90；所以D[5]=60
　　综上，求解顶点V0到其他顶点的最短路径的步骤、最短路径顶点序列和路径长度如表5-8所示。

表5-8 从顶点V0到各终点的D值和最短路径求解过程

	第1步		第2步		第3步		第4步
	距离	路径	距离	路径	距离	路径	距离	路径
V0	0		0		0		0
V1	∞		∞		∞		∞
V2	10	V0,V2	10	V0,V2	10	V0,V2	10	V0,V2

续表

	第1步		第2步		第3步		第4步
	距离	路径	距离	路径	距离	路径	距离	路径
V3	∞		60	V0,V2,V3	50	V0,V4,V3	50	V0,V4,V3
V4	30	V0,V4	30	V0,V4	30	V0,V4	30	V0,V4
V5	100	V0,V5	100	V0,V5	90	V0,V4,V5	60	V0,V4,V3,V5

（4）算法分析
此算法的时间复杂度为O( )。
2．求每一对顶点之间的最短路径
对每一个顶点都调用一次迪杰斯特拉算法，即可得出每一个顶点之间的最短路径，此时算法的时间复杂度为O( )。