最短路问题的Floyd算法的若干讨论

第22卷　第5期

Vol . 22　No . 5　　　　　　　　重庆工学院学报(自然科学) Journal of Chongqing Institute of Technology (Natural Science ) 2008年5月Ma y 2008

最短路问题的Floyd 算法的若干讨论

郝自军1, 何尚录2

(1. 北方民族大学信息与计算科学学院, 银川　750021;

2. 兰州交通大学数理与软件工程学院, 兰州　730070)

摘要:对不含负回路的网络中所有顶点对之间的最短路问题, 通常采用Floyd 算法. 对此算法进行

了讨论, 并对Floyd 算法的计算过程作了一点改进. 改进后的算法对阶数不太大的网络进行较简

单的计算就能得出所有顶点对之间的最短路.

关　键　词:Floyd 算法; 最短路问题; 网络最优化

中图分类号:O157. 1　　　　文献标识码:A 文章编号:1671-0924(2008) 05-0156-04

Some Discussions on Floyd Algorithm

HAO Zi -jun 1, HE Shang -lu 2

(1. School of In formation and Calculating Science , North University for Nationalities , Yinchuan 750021, China ;

2. School of Mathematics , Phys ics &Software En gineering , Lanzhou Jiaotong Universit y , Lanzhou 730070, China )

A bstract :Floyd algorithm is usually used in shortest path when a graph does not include negative circuit . This article first discusses this algorithm , and then gives some modification of the calculating process of this algorithm . The modified algorithm can produce the shortest paths between peaks with simple calculation when it c omes to net w or ks with not too big number of orders .

Key words :Floyd Algorithm ; shortest path

　　最短路问题是网络最优化中一个基本而又非常重要的问题, 这一问题相对比较简单, 在实际生产和生活中经常遇到, 许多的网络最优化问题可以化为最短路问题, 或者用最短路算法作为其子程序. 因此, 最短路的用途已远远超出其表面意义[1-2]迄今为止, 所有最短路算法都只对不含负回路的网络有效, 实际上对含有负回路的网络, 其最短路问题是NP 困难的[2-3], 因此本研究所讨论的网络也不含负回路. 此外, 如果将无向图每条边用两条端点相同、方向相反的弧来代替, 可以将其化为有向图, 因而不讨论无向图. 本研究中未述及的术语、记号可参见文献[2]. 　 　收稿日期:2008-02-20

基金项目:北方民族大学科研项目(2007Y044) .

作者简介:郝自军(1978—), 男, 宁夏灵武人(回族) , 硕士, 讲师, 主要从事运筹与优化的研究.

郝自军, 等:最短路问题的Floyd 算法的若干讨论　　　　　　　　157

1　相关定义及准备

　　定义1[1, 3]　一个有向图D 是由一个非空的有限集合V (D ) 和V (D ) 中某些元素的有序对集合A (D ) 构成的二元组, 记为D =(V (D ) , A (D ) ) , 简记为D =(V , A ) . 其中:有限集合V ={v 1, v 2, …,v n }为D 的顶点集; A ={a 1, a 2, …,a m }为D 的弧集, A 中每个元素a k 都是V (D ) 中某2个元素v i 和v j 的有序对, 记为a k =(v i , v j ) .

如果给有向图D 中的每条弧都赋一个或多个实数值, 得到的有向图称为赋权有向图或有向网络, 简称为网络, 并记为D =(V , A , W ) .

定义2[2]　设D =(V , A , W ) 是一个赋权有向图, v i 和v j 是D 中2个顶点, D 中所有(v i , v j ) 路中权最小的路称为最短(v i , v j ) 路.

假设网络D =(V , A , W ) 不含负回路, 顶点集V ={v 1, v 2, …,v n }, 先考虑特定顶点v 1到其它各顶点的最短路. D 中最短(v 1, v n ) 路的线性规划模型为:min (v , ∑w ij x i j v ) ∈A i j (1)

1i =1

2≤i ≤n -1

i =n (2) j :(v , v ) ∈A i j ∑x ij -j :∑x j i 0(v , v ) ∈A j i -1

(3)

其中:条件(1) 中w ij 代表弧(v i , v j ) 的权; 条件(2) 则代表在(v 1, v n ) 路上除了顶点v 1只有一条出弧、v n 只有一条入弧以外, 其余的顶点出弧数量与入弧数量相同; 条件(3) 中x ij 取1或0分别代表弧(v i , v j ) 在(v 1, v n ) 路上的次数. 对于一般的(v 1, v i ) 路(i =1, 2, …, n ) , 可以将条件(1) ～(3) 做适当变换得到类似的线性规划模型. 显然如果能解出(1) ～(3) , 则最短(v 1, v n ) 路的长就是目标函数的值, 而根据x i j 的取值也可以定出最短(v 1, v n ) 路. 但不幸的是这样做并不能带来很大帮助. 通常可以将条件(1) ～(3) 化为其对偶规划, 也可以根据下述定理化为一个方程.

定理1[2]　设D =(V , A , W ) 是一个不含非正回路的网络, 顶点集V ={v 1, v 2, …,v n }, 且D 中存在(v 1, v i )

(i =1, 2, …, n ) 路, 则u j 是D 中最短(v 1, v j ) (j =1, 2, …,n ) 路的长, 当且仅当(u 1, u 2, …, u n ) 满足:

u 1=0

u j =(v min (u i +w ij ) 　j =2, 3, …, n , v ) ∈A i j x ij =0或1　　　(对 (v i , v j ) ∈A ) (4)

为了方便, 这里约定对某个(v i , v j ) A , 令w i j =+∞,这样式(4) 等价于

u 1=0

u j =min (u k +w kj ) 　j =2, 3, …,n k ≠j (5)

　　方程(5) 称为最短路方程, 它是一个非线性方程组, 求u j 时必须知道所有其它的u k , 故直接求解式

(5) 是相当困难的, 因而将最短路问题化为方程(5) 似乎并没有什么好处, 但可以以它为基础得到特定顶点到其他各顶点最短路的各种算法. 对于特殊的无回路网络、非负权网络和一般的不含回路的网络, 分别可以用代换法、Dijkstra 算法和Ford 算法求出顶点v 1到其他各顶点之间的最短路, 具体可见文献[2]. 2　Floyd 算法及在计算中的改进, ,

158　　　　　　　　重庆工学院学报

V ={v 1, v 2, …,v n }. Floyd 算法就是解决这类问题的. 当然这个问题可以在一定条件下反复应用已有的代换法、Dijkstra 算法和Ford 算法, 第1次求从v 1到v 2, v 3, …,v n 的最短路, 第2次求从v 2到v 1, v 3, …,v n 的最短路, …, 第n 次求从v n 到v 1, v 2, …, v n -1的最短路. 这样就得到D 中所有顶点对之间的最短路. 但这样做程序复杂且计算量大, 计算量为O (n ) , 而如果用Floyd 算法, 可以达到简化复杂计算的目的.

在不含负回路的网络D =(V , A , W ) 中, 对一切(v i , v j ) ∈A , w ij 是弧(v i , v j ) 的权, 当(v i , v j ) A 时, Floyd 算法规定:

w ij 0i =j

+∞i ≠j 4

用D (i , j , m ) 表示由顶点集合{v i }∪{v j }∪{v 1, v 2, …,v m }导出的D 的子网络(i , j =1, 2, …,n ) . 特别地D (i , j , 0) 表示由顶点集{v i }∪{v j }={v i , v j }导出的D 的子网络, 把网络D (i , j , m ) 中最短(v i , v j ) 路的长

m ) 记为u (, 则显然有下面的结论:i j

0) 结论1　u (w ij . ij =

n ) 结论2　D (i , j , n ) =D , 因此u (v i , v j ) 路的长. ij 是D 中最短(

m ) m -1) 结论3　D (i , j , m -1) 是D (i , j , m ) 的子网络, 因而u (≤u (. ij ij

结论4　D (i , m , m ) =D (i , m , m -1) , D (m , j , m ) =D (m , j , m -1) , 所以有u i m =u im

m -1) u (. mj (m ) (m -1) , u mj =(m )

有了上述准备及几个重要的结论, 就可以得出以下这个很重要的定理.

定理2[2]　设网络D =(V , A , W ) 不含负回路, 则对一切i , j =1, 2, …,n , 网络D (i , j , m ) 中最短(v i ,

m ) v j ) 路的长u (ij 满足:0) u (=w i j i j

(m ) u i j (m -1) =min {u ij , (m -1) (m -1) u i m +u mj }　(1≤m ≤n ) (6)

(n ) 　　定理2是Floyd 算法的重要依据, 让m 从1循环到n 就可以得到网络D 中最短(v i , v j ) 路的长u i j .

为了在计算网络D (i , j , m ) 中最短(v i , v j ) 路的长的同时求出D (i , j , m ) 中最短(v i , v j ) 路, 引进一个正向追踪法:

m ) m ) (m ) (0) 令P (i , j , m ) 中最短(v i , v j ) 路, r (j . 如果ij 是网络D (ij 表示P ij 的第一条弧的头的下标, 显然r ij =

m -1) m -1) m -1) m -1) m ) m -1) m ) m -1) m ) r (已经知道, 当u (≤u (+u (时, 则u (=u (, 因而有r (=r (; 否则r (=i j ij i m mj ij ij ij ij ij m -1) n ) n ) n ) r (. 若r (k , 则P (v i , v k ) , 因为D 不含负回路, 因而P ((v i , v k ) 是D 中最短i m ij =ij 的第1条弧为(ij -

(v k , v j ) 路, 从而P kj 的第1条弧就是P i j 的第2条弧, 依次类推, 可以得到P i j 的所有弧.

因此, Floyd 算法的步骤:

0) 0) Step 0　令u (w ij , r (j (i , j =1, 2, …,n ) , m =1. ij =ij =(n ) (n ) (n )

Step 1　对一切1≤i ≤n , 1≤j ≤n , 令:

(m -1) (m -1) (m -1) (m -1) r 　若u ≤u +u ij ij im mj (m ) (m ) (m -1) (m -1) (m -1) r ij (u i j =min {u ij , u i m +u mj }m -1) (m -1) (m -1) (m -1) ; r im 　若u ij >u im +u mj

Step 2　如果m =n , 结束; 否则置m =m +1, 转Step 1.

基于上述Floyd 算法, 我们在计算中可以将其简化为:

Step 0　令u ij =w ij , r ij =j (i , j =1, 2, …,n ) , m =1.

m ) m ) m ) Step 1　对一切1≤i ≤n , 1≤j ≤n , 令U (=(u (; R (m ) =(r (. ij ) ij )

m -1) 先写出U (m -1) 的第m 行和第m 列的所有元素, 用第m 列的第1个元素u (与第m 行的每个元素1m (0) (0)

u (m -1) 1j 1j 1j (m ) (m -1) , m (m -1) (m -1) 22m (m -1)

郝自军, 等:最短路问题的Floyd 算法的若干讨论　　　　　　　　159

m -1) m ) m -1) (-1) m -1) m 行中的每个元素u ((1≤j ≤n ) 相加, 并取u (min {u (, u 2m +u (}; …;最后用第m 列m j 2j =2j m mj

的第n 个元素u nm

u mj (m -1) (m -1) (m ) 与第m 行中的每个元素u mj (m ) (m -1) (1≤j ≤n ) 相加, 并取u nj =min {u nj

(m ) (m -1) (m ) (m -1) , u nm (m -1) +}. 新的u ij 组成矩阵U . (m -1) 对于某些k , l , 若有u k l (m -1) >u k m +u ml (m -1) , 则u kl =u km +u ml (m -1) , 此时在u kl 下端划一横(m )

m -1) m -1) 线. 在R (m -1) 的相应于U (m ) 中所有划横线的元素位置(k , l ) 处, 将R (的元素r (变为该行的第m kl

m -1) m -1) m ) 列的元素r (, 并将R (变为R (km

Step 2　如果m =n , 结束; 否则置m =m +1, 转Step1.

这样我们对阶数不太大的网络进行较简单的计算就能得出所有顶点对之间的最短路.

参考文献:

[1]　运筹学教材编写组. 运筹学[M ]. 2版. 北京:清华大学出版社, 1990.

[2]　谢政. 网络算法与复杂性理论[M ]. 长沙:国防科技大学出版社, 2004.

[3]　谢金星, 邢文训. 网络优化[M ]. 北京:清华大学出版社, 2000.

(责任编辑　刘　舸)

(上接第146页)

对式(6) 取模31601, 得剩余序列周期为20, 当n ≡8, 9, 18, 19(mod20) 时, -u n +7v n ≡±619, ±31

=-(mod31601) . 由式(6) 得1, 1, 矛盾, 所以式(6) 无解. [**************]

综合1) 和2) 的结论知, 式(1) 仅有正整数解(x , y ) =(7, 1) .

证明完毕. 2

参考文献:

[1]　COHN J H E . Some Quartic Diophantine Equations [J ]. Pacific J M ath , 1968, 26; 233-243.

[2]　TZANAKIS N . On the Diophantine Equation y 2-D =2n [J ]. Number Theory , 1983, 17:144-164.

[3]　黎进香, 张春蕊. 关于不定方程的初等解法[J ]. 哈尔滨工业大学学报, 1995(5) :13-16.

[4]　柯召, 孙琦. 数论讲义[M ]. 北京:高等教育出版社, 2001.

[5]　罗明. 关于不定方程x 3+1=7y 2[J ]. 重庆师范学院学报:自然科学版, 2003, 20(1) :5-7.

(责任编辑　刘　舸)