求解无向图最短路的方法

狄克斯特拉(Dijkstra)标号算法(以下简称D算法)是狄克斯特拉在1959年提出的,适合于求解所有弧权wij≥0的最短路问题。其基本思想是:最短路的子路一定还是最短路。规定:始点为vs,终点为vt;T标号为临时性标号;P标号为永久性标号。永久性标号表示从点vs到vj(j＝1,2,…,t)的最短路权;临时性标号表示从点vs到vj最短路权的上界。

无向图最短路(链)的D算法步骤为:

(1)对始点vs做P标号:P(vs)＝0;同时对其余各点均做T标号:T(vj)＝∞。

(2)对于已做P标号的点,考虑与之相邻的点(不含已做P标号的点),修改T标号:T′(vj)＝min[T(vj),P(vi)＋wij]。

(3)比较所有已做T标号的点,对权最小的T标号做P标号:P(vj)＝min[T(vj)]。

(4)当所有点都做了P标号,计算停止,否则转到步骤(2),直到求出最短路。

【例6-4】用D算法求图6-21中vs到vt的最短路。

图6-21

解:

①如图6-22所示,对始点vs做P标号:P(vs)＝0,在(0)下面画一横线,表示对始点vs已做P标号;对其余各点做T标号:T(vj)＝∞,j＝1,2,3,4,5,t。

图6-22

②对于已做P标号的点vs,考虑与之相邻的点,修改T标号:T′(vj)＝min[T(vj),P(vi)＋wij],如图6-23所示,其中,T′(v1)＝min[T(v1),P(vs)＋ws1]＝min[∞,0＋2]＝2;T′(v3)＝min[T(v3),P(vs)＋ws3]＝min[∞,0＋4]＝4。

③比较所有已做T标号的点,对权最小的T标号做P标号:P(vj)＝min[T(vj)]。如图6-23所示,P(vj)＝min[2,4,∞,∞,∞,∞]＝P(v1)＝2,在(2)下面画一横线,表示已做P标号。(www.xing528.com)

图6-23

④对已做P标号的点v1,考虑与之相邻的点,修改T标号:T′(vj)＝min[T(vj),P(vi)＋wij],如图6-24所示,其中T′(v2)＝min[T(v2),P(v1)＋w12]＝min[∞,2＋2]＝4,T′(v4)＝min[T(v4),P(v1)＋w14]＝min[∞,2＋7]＝9。

图6-24

⑤比较所有已做T标号的点,对权最小的T标号做P标号:P(vj)＝min[T(vj)],如图6-25所示,P(vj)＝min[4,4,9,∞,∞,∞]＝P(v2)＝P(v3)＝4。先对点v2做P标号,同时修改v4的标号。

图6-25

再对点v3做P标号,由于相邻点已做P标号,不能再做修改,同时T′(v5)＝min[T(v5),P(v3)＋w35]＝min[7,4＋4]＝7,因此不用修改标号。重复上述步骤,最终标号结果如图6-26所示。

图6-26

最后,按标号寻找从vs到vt的最短路(链),从vt开始向前依次寻找最短路中的各条边,如图6-26所示,vs→v1→v2→v5→v4→vt为从vs到vt的最短路(链),总权为13。需要说明的是,使用D算法,不仅可以求出网络中从始点到终点的最短路径和路权,而且可以求出从始点到各个点的最短路径和最短路权。对于本例,从始点到其他各点的最短路径和最短路权如表6-2所示,其中,只有vs→v3不是从vs到vt最短路的子路,这符合D算法的基本思想:“最短路的子路一定还是最短路”。

表6-2

需要指出的是,最短路问题与最小树问题有区别,由图6-16可知,最小树方案(权为14)必须包括原图中所有结点,但最短路方案(权为13)一般不包括所有结点。