从到的最短路是如何修改的？最短路算法

本节将介绍在一个赋权有向图中寻求最短路的方法，这些方法实际上求出了从给定一个点 vs到任一个点 vj的最短路。如下事实是经常要利用的。

如果P 是D中从 vs到 vj的最短路，vi是P中的一个点，那么，从 vs沿P 到 vi的路是从vs到 vi的最短路。

事实上，如果这个结论不成立，设Q 是从 vs到 vi的最短路，令P′是从 vs沿Q 到达 vi，再从 vi沿P 到达 vj的路，那么，P′的权就比P的权小，这与P 是从 vs到 vj的最短路矛盾。

下面先介绍在所有wij≥0的情形下，求最短路的方法。当所有的wij≥0时，目前公认的最好方法是由Dijkstra 于1959 年提出来的Dijkstra 方法。其基本思想是从 vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从 vs到该点的最短路的权（称为P 标号），或者是从 vs到该点的最短路的权的上界（称为T 标号）；方法的每一步是去修改T 标号，并且把某一个具T 标号的点改变为具P 标号的点，从而使D中具P 标号的顶点数多一个，这样，至多经过p-1步，就可以求出从 vs到各点的最短路。

在叙述Dijkstra 方法的具体步骤之前，以例6-10 为例来说明这个方法的基本思想。例6-10中，s=1。因为所有wij≥0，故有d（v1，v1）=0。这时，v1是具P 标号的点。现在考查从 v1发出的三条弧：（v1，v2），（v1，v3）和（v1，v4）。如果某人从 v1出发沿（v1，v2）到达 v2，这时需要d（v1，v1）+w12=6单位的费用；如果他从 v1出发，沿（v1，v3）到达 v3，则需要d（v1，v1）+w13=3单位的费用；类似地，若沿（v1，v4）到达 v4，需要d（v1，v1）+w14=1单位的费用。因

可以断言，他从 v1出发到 v4所需要的最小费用必定是1 单位，即从 v1到 v4的最短路是（v1，v4），d（v1，v4）=1。这是因为从 v1到 v4的任一条路P，如果不是（v1，v4），则必是先从 v1沿（v1，v2）到达 v2，或者沿（v1，v3）到达 v3，而后再从 v2或者 v3到达 v4；但如上所说，这时候他已需要6单位或3 单位的费用，不管他如何再从 v2或者从 v3到达 v4，所需要的总费用都不会比1 少（因为所有的wij≥0）。因而推知d（v1，v4）=1，这样就可以使 v4变成具P 标号的点。

现在考查从 v1及 v4指向其余点的弧。由上已知，从 v1出发，分别沿（v1，v2），（v1，v3）到达v2，v3，需要 6 单位或 3 单位的费用，而从 v4出发沿（v4，v6）到达 v6，所需要的费用是d（v1，v4）+w46=1+10=11单位，因

基于同样的理由可以断言，从 v1到 v3的最短路是（v1，v3），d（v1，v3）=3。这样又可以使点 v3变成具P 标号的点。如此重复这个过程，可以求出从 v1到任一点的最短路。

在下述Dijkstra 方法的具体步骤中，用P，T 分别表示某个点的P 标号和T 标号，Si表示第i 步时，具P 标号点的集合。为了在求出从 vs到各点的距离的同时，也求出从 vs到各点的最短路，给每个点v 以一个λ值，算法终止时，如果 λ（v）=m，表示在从 vs到v的最短路上，v的前一个点是 vm；如果 λ（v）=M，则表示D中不含从 vs到v的路；λ（v）=0表示v=vs。

Dijkstra 方法的具体步骤如下：

给定赋权有向图D=（V，A），开始（i=0），令 S0={vs}，P（vs）=0，λ（vs）=0，对每一个v≠vs，令 T（v）=+∞，λ（v）=M，令k=s。

第一步：如果 Si=V，算法终止。对每个v ∈Si，d（vs，v）=P（v）；否则转入第二步。

第二步：考查每个使（vk，vj）∈A且 vj∉ Si的点 vj。

如果 T（vj）＞P（vk）+wkj，则把 T（vj）修改为P（vk）+wkj，把 λ（vk）修改为k；否则转入第三步。

第三步：令 T（vji）=

如果则把的T 标号变为P 标号把i 换成 i+1，转入第一步；否则终止，这时对每一个v ∈Si，d（vs，v）=P（v），而对每一个v ∉ Si，d（vs，v）=T（v）。

现在用Dijkstra 方法求例6-10中从 v1到各个顶点的最短路，这时s=1。

（1）i=0。

S0={v1}，P（v1）=0，λ（v1）=0，T（vi）=+∞，λ（vi）=M，i=2，3，…，9，以及k=1。

转入第二步，因（v1，v2）∈A，v2∉ S0，P（v1）+w12＜T（v2），故把T（v2）修改为P（v1）+w12=6，把λ（v2）修改为1；同理，把T（v3）修改为P（v1）+w13=3，把λ（v3）修改为1；把T（v4）修改为P（v1）+w14=1，把λ（v4）修改为1。

转入第三步，在所有的T 标号中T（v4）=1 最小，于是令P（v4）=1，令 S1=S0∪{v4}={v1，v4}，k=4。

（2） i=1。

转入第二步，把T（v6）修改为P（v4）+w46=11，把λ（v6）修改为4。

转入第三步，在所有的T 标号中，T（v3）=3最小，于是令P（v3）=3，令 S2={v1，v4，v3}，k=3。

（3）i=2。

转入第二步，因（v3，v2）∈A，v2∉ S2，P（v3）+w32＜T（v2），把T（v2）修改为P（v3）+w32=5，把λ（v2）修改为3。

转入第三步，在所有的T 标号中，T（v2）=5最小，于是令P（v2）=5，S3={v1，v4，v3，v2}，k=2。

（4）i=3。

转入第二步，把T（v5）修改为P（v2）+w25=6，把λ（v5）修改为2。

转入第三步，在所有的T 标号中，T（v5）=6最小，于是令P（v5）=6，S4={v1，v4，v3，v2，v5}，k=5。

（5）i=4。

转入第二步，把T（v6），T（v7），T（v8）分别修改为10，9，12，把λ（v6），λ（v7），λ（v8）修改为5。

转入第三步，在所有的T 标号中，T（v7）=9最小，于是令P（v7）=9，S5={v1，v4，v3，v2，v5，v7}，k=7。

（6）i=5。

转入第二步，（v7，v8）∈A，v8∉ S5，但因P（v7）+w78＞T（v8），故T（v8）不变。

转入第三步，在所有的T 标号中，T（v6）=10最小，令P（v6）=10，S6={v1，v4，v3，v2，v5，v7，v6}，k=6。

（7）i=6。

转入第二步，从 v6出发没有弧指向不属于 S6的点，故直接转入第三步。

转入第三步，在所有的T 标号中，T（v8）=12最小，令P（v8）=12，S6={v1，v4，v3，v2，v5，v7，v6，v8}，k=8。

（8）i=7。

转入第三步，这时仅有的T 标号点为v9，T（v9）=+∞，算法终止。

算法终止时，

这表示对 i=1，2，…，8，d（v1，vi）=P（vi），而从 v1到 v9不存在路，根据λ值可以求出从 v1到 vi的最短路（ i=1，2，…，8）。例如，为了求从 v1到 v8的最短路，考查λ（v8），因λ（v8）=5，故最短路包含弧（v5，v8）；再考查λ（v5），因λ（v5）=2，故最短路包含弧（v2，v5）；依此类推，λ（v2）=3，λ（v3）=1，于是最短路包含弧（v3，v2）及（v1，v3），这样从 v1到 v8的最短路是（v1，v3，v2，v5，v8）。

上面介绍了求一个赋权有向图中，从一个顶点 vs到各个顶点的最短路。对于赋权无向图G=（V，E），因为沿边[vi，vj]既可以从 vi到达 vj，也可以从 vj到达 vi，所以边[vi，vj]可以看作两条弧（vi，vj）及（vj，vi），它们具有相同的权 w[vi，vj]。这样，在一个赋权图中，如果所有的wij≥0，只要把Dijkstra 方法中的“第二步考查每个使（vk，vj）∈A且 vj∉ Si的点 vj”改为“第二步考查每个使[vk，vj]∈E且 vj∉ Si的点 vj”，同样地可以求出从 vs到各点的最短路（对于无向图，就是最短链）。

例6-11　用Dijkstra 方法求图6-20 所示的赋权图中，从 v1到 v8的最短路。

解　这里只写出计算的最后结果，具体步骤留给读者去完成。

这样从 v1到 v8的最短链为（v1，v3，v2，v5，v9，v8），总权为11。

现在来证明Dijkstra 方法的正确性。只要证明对于每一个点v ∈Si，P（v）是从 vs到v的最短路的权，即 d（vs，v）=P（v）即可。

图6-20

对i 施行归纳。当i=0时，结论显然正确。(www.xing528.com)

设当i=n时，结论成立，即对每一个v ∈Sn，d（vs，v）=P（v）。现在考查i=n+1时，因所以只要证明即可。根据算法，是这时具最小T 标号的点，即

这里为了清晰起见，用 Tn（v）表示当i=n执行第三步时点v的T 标号。假设H 是D中任一条从 vs到的路，因为vs∈Sn，而 vj∉ Sn，那么从 vs出发，沿H 必存在一条弧，它的始点属于 Sn，而终点不属于 Sn。假设（vr，vl）是第一条这样的弧，

由归纳假设，P（vr）是从 vs到 vr的最短路的权，于是

根据方法中T 标号的修改规则，因 vr∈Sn，vl∉ Sn，故

这就证明了的最短路的权，由方法知，这样就证明了

Dijkstra 算法只适用于所有wij≥0的情形，当赋权有向图中存在负权时，算法失效。例如，在图6-21 所示的赋权有向图中，如果用Dijkstra 方法，可得出从 v1到 v2的最短路的权是1，但这显然是不对的，因为从 v1到 v2的最短路是（v1，v3，v2），权是-1 。

图6-21

下面介绍在赋权有向图D中，存在具负权的弧时，求最短路的方法。

为方便起见，不妨设从任一点 vi到任一点 vj都有一条弧（如果在D中，（vi，vj）∉ A，则添加弧（vi，vj），令 wij=+∞）。

显然，从 vs到 vj的最短路总是从 vs出发，沿着一条路到达某个点 vi，再沿（vi，vj）到达 vj（这里 vi可以是 vs本身）。由6.3.2 节开始介绍的结论可知，从 vs到 vi的这条路必定是从 vs到vi的最短路，所以 d（vs，vj）必满足如下方程：

为了求得这个方程的解d（vs，v1），d（vs，v2），…，d（vs，vp）（这里p=p（D）），可用如下递推公式：

开始时，令

若进行到某一步，例如第k 步时，对所有j=1，2，…，p，有

例6-12　求图6-22 所示的赋权有向图中从点 v1到各点的最短路。

图6-22

解　利用上述递推公式，求解结果如表6-1 所示（表中未写数字的空格内是+∞）。

表6-1

可以看到，当t=4时，对所有j=1，2，…，8，有

于是表中最后一列0，-5，-2，-7，-3，-1，-5，6就分别是从 v1到 v1，v2，…，v8的最短路的权。

为了进一步求得从 vs到各点的最短路，可以类似于Dijkstra 方法中，给每一个点以λ值开始：

则把这时的λ（vj）修改为i0。迭代终止时，根据各点的λ值，可以得到从 vs到各点的最短路。

寻求最短路的另一个办法是在求出最短路的权以后，采用“反向追踪”的方法。比如，已知 d（vs，vj），则寻求一个点 vk，使 d（vs，vk）+wkj=d（vs，vj），记录下（vj，vk）；再考查 d（vs，vk），寻求一点 vi，使 d（vs，vi）+wik=d（vs，vk），如此等等，直至到达 vs为止，于是从 vs到 vj的最短路是（vs，…，vi，vk，vj）。

如例6-12，由表6-1 已知，d（v1，v8）=6，因d（v1，v6）+w68=（-1）+7=d（v1，v8），故记下（v6，v8）；

因d（v1，v3）+w36=d（v1，v6），故记下（v3，v6）；

因d（v1，v1）+w13=d（v1，v3），故记下（v1，v3），

从而从 v1到 v8的最短路是（v1，v3，v6，v8）。

定义5　设D 是赋权有向图，C 是D中的一个回路，如果C的权 w（C）小于零，则称C 是D中的一个负回路。

不难证明：

（1）如果D 是不含负回路的赋权有向图，那么，从 vs到任一点的最短路必可取为初等路，从而最多包含p-2个中间点；

（2）上述递推公式中的d（t）（vs，vj）是在至多包含 t-1个中间点的限制条件下，从 vs到 vj的最短路的权。

由（1）、（2）可知：当D中不含负回路时，上述算法最多经过p-1次迭代必定收敛，即对所有的j=1，2，…，p，均有 d（k）（vs，vj）=d（k-1）（vs，vj），从而求出从 vs到各个顶点的最短路的权。

如果经过p-1次迭代，存在某个j，使 d（p）（vs，vj）≠d（p-1）（vs，vj），则说明D中含有负回路。显然，这时从 vs到 vj的路的权是没有下界的。

为了加快收敛速度，可以利用如下的递推公式。

J.Y.Yen 提出了一个改进递推算法：

对t=2，4，6，…，按j=1，2，…，p的顺序计算：

对t=3，5，7，…，按j=p，p-1，…，1的顺序计算：

同样地，当对所有的j=1，2，…，p，当

时，算法终止。