v*?v4，d(v1,v4)?L4(v*)?minL4(vj)?5，A?{v1,v2,v3,v4}，前列顶点v3；

v?Vvj k?5 v1v22*v?Vv34*v45*v55*v6v7 L5(vj) 0*??11 v*?v5，d(v1,v5)?L5(v*)?minL5(vj)?5，A?{v1,v2,v3,v4,v5}，前列顶点

v2；

vj k?6 v1v22*v?Vv34*v45*v55*v6v7 L6(vj) 0*??11* v*?v7，d(v1,v7)?L6(v*)?minL6(vj)?11，A?{v1,v2,v3,v4,v5,v7}，前列顶点v4；

vj k?7 v1v22*v?Vv34*v45*v5v6v7 11* L7(vj) 0*5*??*v*?v6，d(v1,v6)?L7(v*)?minL7(vj)???，因此v1到v6没有最短路。 综合以上过程，得到顶点v1到其余各顶点的最短路径及其长度，如图9-6所示。

v2[2]3v5[5]2 v1[0]21v4[5]6v7[11]v3[4]3v6[??]

图9-6

2、逐次逼近算法

Dijkstra算法只能给出无负赋权有向图的最短路径，对于出现了负赋权弧的网络，通常使用逐次逼近算法。

最短路性质：若序列{v1,v2,?,vn}是从v1到vn的最短路，则序列

13

{v1,v2,?,vn?1}必为从v1到vn?1的最短路，序列{v1,v2,?,vi}也必为从v1到vi的最短路。如果令Pij为vi到vj的最短路径长度，则P1i为v1到vi最短路径长度，且

P1j?min(P1i?wij)

i其中wij?w(vi,vj)为边(vi,vj)的长度，当vi与vj之间无边时，wij???。上述方程可以构造逐次逼近法进行迭代，逐次逼近算法的基本步骤：

第1步：输入wij，i,j?1,2,?n，P1(j1)?w1j,(j?1,2,?,n)，k?1； 第2步：P1(jk?1)?min(P1(ik)?wij)，j?1,2,?n；

i第3步：若P1(jk?1)?P1(jk)(j?1,2,?,n)时，迭代终止，并且P1j?P1(jk?1)

(j?1,2,?,n)即是v1到vj的最短路径长度，否则k?k?1，转第二步。

例9-5 已知某地区的交通网络如图9-7所示，其中顶点代表村镇，边代表公路，wij为村镇间公路的距离（单位：公里），现该地区要建立一座中学，为了方便学生就学，问应该将学校建立在那个村镇，可使距离学校最远的村镇的学生上学时所经过的路程最近？

v3623v5v4v1322.51.81.51.5v6v7v2图9-7

解：本问题是一个选址问题，也可以归结为每点到各点的最短路问题。首先应该求出每个顶点到其余各顶点的最短路，然后再比较，最后选出符合要求的村镇建立学校。

我们以顶点v6为例，求顶点v6到其余各顶点的最短路，使用逐次逼近法求解。初始条件为

(1)(1)(1)(1)(1)(1)(1)P61???,P62?1.5,P63?2.5,P64?1.8,P65???,P66?0,P67?1.5

开始进行迭代，结果见表9-1。

表9-1

14

jwij )(2)(3)P6(1j P6j P6j iv1 v2 v3 v4 v5 v6 v7 v1 v2 0 3 3 0 ?? ?? ?? ?? ?? ?? 4.5 3 0 4.5 1.5 2.5 1.8 4.8 0 1.5 ?? ?? 1.5 ?? 1.5 2 0 3 6 3 0 2.5 ?? 2.5 1.8 ?? 1.8 1.5 2.5 1.8 v3 v4 ?? 2 ?? ?? 2 v5 v6 v7 ?? ?? 6 ?? 1.5 2.5 ?? ?? ?? 4.8 0 1.5 0 0 1.5 0 1.5 1.8 ?? ?? ?? ?? ?? ?? 1.5 迭代到第3步时，P6(j3)?P6(j2)，j?1,2,?,7，迭代终止，顶点v6到vj的最短路径，长度在表9-1的最后一列。

同样可以求出顶点v1,v2,v3,v4,v5,v7到其余顶点vj的最短路，结果见表9-2。

表9-2 距离vi最远的村镇距离 9.3 6.3 5 6.3 9.3 4.8* 6.3 村镇 v1 v2 v3 v4 v5 v6 v7 0 3 5 6.3 9.3 4.5 6 3 0 2 3.3 6.3 1.5 3 5 2 0 2 5 2.5 4 6.3 3.3 2 0 3 1.8 3.3 9.3 6.3 5 3 0 4.8 6.3 4.5 1.5 2.5 1.8 4.8 0 1.5 6 3 4 3.3 6.3 1.5 0 v1 v2 v3 v4 v5 v6 v7

由于所有村镇到村镇v6的最长距离中4.8公里是最小的，因此应该在村镇v6 15

建立学校，可使距离学校最远的村镇的学生上学时所经过的路程最近。

3、Floyd算法

Dijkstra算法和逐次逼近法可以给出网络从某一起始顶点到其他顶点的最短路，但是某些问题中，要求网络中任意两顶点间的最短路。Floyd算法不仅能求某一点到其他各点的最短路，还能求各点到某一点的最短路和任意两顶点间的最短路。在Floyd算法中权值wij正负不限。

设D?(V,E,w)是一个赋权有向图，其中V?{v1,v2,?,vn},wij为弧(vi,vj)的权重，当vi和vj间没有弧相连时wij??。构造网络的权矩阵W?(wij)n?n，其中

?wijwij????(vi,vj)?E(vi,vj)?E

Floyd算法基本步骤：

第1步：输入权矩阵W?(wij)n?n，对所有i,j,dij?wij；当wij??，pij?0，否则pij?j；k?1。

第2步：更新dij和pij。

对所有i,j，若dik?dkj?dij，转第3步，否则dij?dik?dkj,pij?pik，

k?k?1，继续第3步。

第3步：如果k??n，转第2步。

第4步：输出最短路距离矩阵，d?(dij)n?n和最短路径矩阵P?(pij)n?n。 例9-6 用Floyd算法求图9-8所示网络中各顶点间的最短距离。

v23v52v47v123649v78524v3v6

图9-8

解: 写出权矩阵和路径矩阵：

16