經典Bellman-Ford算法的改進及其實驗評估

韓偉一

(哈爾濱工業大學經濟與管理學院，150001 哈爾濱)

經典Bellman-Ford算法的改進及其實驗評估

韓偉一

(哈爾濱工業大學經濟與管理學院，150001 哈爾濱)

針對以高效求解有邊數限制的最短路問題，對經典Bellman-Ford算法進行了改進.借鑒劃分算法的思想，通過減少距離標號的數目，得到了兩個改進算法.既然已有的改進算法均不能解決有邊數限制的最短路問題，因而本算法是經典Bellman-Ford算法的全新改進.相對于經典Bellman-Ford算法，改進后的算法不僅可有效地節省存儲空間，而且實驗表明能顯著地提高計算效率.

算法;Bellman-Ford算法;劃分算法;最短路問題

Bellman-Ford算法一般有兩種表述，一種為經典的動態規劃模式或經典算法［1－3］，另外一種為劃分模式或劃分算法(Partitioning algorithm)［4－7］.嚴格意義上，劃分算法并不是普遍公認的經典Bellman-Ford算法，而是經過改進的Bellman-Ford算法，它把參與第i輪和第i+1輪迭代的點進行了明確劃分，改進了距離標號的計算方式，能夠顯著提高計算效率.目前，采用先進先出策略的劃分算法是解決負權最短路問題、最短路問題可行性問題的最有競爭力的算法，在算法基礎上再加入門檻技術即成為解決負權最短路問題當前公認的最快算法［8－9］.盡管經典的Bellman-Ford算法在解決負權最短路問題、最短路問題可行性問題已經不具有優勢，但它仍然是解決有邊數限制最短路問題的最好算法［10－11］.本文將研究經典Bellman-Ford算法及其性質，并將對之進行改進，使之能更快地解決有邊數限制最短路問題，同時將對改進后的算法進行實驗評估.

1 經典Bellman-Ford算法的兩種形式及其性質

對于一個具有n個點、m條邊的有向圖G(V，E)，n個點分別以1，2，…，n為編號，且規定點1為始點，w(i，j)為有向邊(i，j)的權.定義dk(i)為點i在第k次迭代后i點的距離標號，則可給出經典Bellman-Ford算法的常見形式為:

Step 1 初始化.令 d0(1)=0，d0(i)=+∞，(2≤i≤n).

Step 2 對每一條邊(i，j)按照給定順序進行計算

Step 3 當所有的點i(1≤i≤n)均滿足dt-1(i)=dt(i)，(t≤n)時，dt(i)就是從點1到i的最短距離;當存在某個點j滿足dn-1(j)≠dn(j)時，可判定存在負循環，算法結束.

對于以上形式的Bellman-Ford算法，可作兩方面的改進:1)當dk-1(i)=dk-2(i)時，在第k次迭代中Step 2中邊(i，j)所進行的計算不會造成點j的距離標號的改變，從而對邊(i，j)所進行的計算可以省略，這樣可把 Step 2的計算量由Θ(m)降低為O(m);2)算法結束的判定規則相對復雜，計算量比較大，可作進一步改進.

定義Ak為在第k-1輪迭代中距離標號減少的點的集合，則經典Bellman-Ford算法又可采取下列精簡形式為:

Step 1 初始化.令 d0(1)=0，d0(i)=+∞，(2≤i≤n)，把所有點加入集合A1.

Step 2 對于任意點i(1≤i≤n)，令dk(i)=dk-1(i).

Step 3 按照進入順序對Ak中的各點i進行計算為

如果dk(j)＜dk-1(j)，且當點j?B時，則把點j加入集合Ak+1.

Step 4 如果集合Ak+1=?，則算法結束，d(i)就是從點1到i的最短距離;當集合Ak+1≠?，且k=n-1時，可判定存在負循環，算法結束;當集合Ak+1≠?，且k＜n-1時，執行Step 5.

Step 5 令k=k+1，轉到Step 2.

關于經典Bellman-Ford算法的高效實現，文獻［8，11］分別介紹了Bellman本人的改進思想，但已有的改進算法均不適用于有邊數限制最短路問題，且沒有專門論述此問題.上述精簡形式可解決有邊數限制最短路問題，相對于常見形式計算效率有了顯著地改進.

經典Bellman-Ford算法無論采用上述哪種形式，都具有以下性質:

性質1 算法的迭代次數為最短路徑樹的深度.

性質2 算法每次迭代的計算量均為O(m).

性質3 算法的最壞計算復雜性為O(nm).

性質4 算法經過n-1次迭代后就可判定負循環的存在.

上述4個性質已經由相關文獻證實，本文不給出具體證明.但針對性質1將給出以下結論:

定理1 算法在k次迭代后，如果dk(i)＜+∞，那么可得到從始點1到j的邊數≤k的一條最短路徑，這條路徑的長度恰為dk(i).

證明 用數學歸納法證明，顯然k=1時，命題成立.

假設k=t-1時，命題仍然成立.假定從始點1到j的邊數≤t的最短路徑中，點j的上一個點為i(i≠j).這樣一來，要獲得從始點1到j的邊數≤t的最短路徑，就必須首先獲得從始點1到j(j≠i)的邊數≤t-1的最短路徑.那么當k=t時

情形1 如果dt(j)＜dt-1(j)，由常見形式的Step 2，則有

根據上述假定，那么必有dt(j)=dt-1(i)+w(i，j).再根據歸納法的假設，dt-1(h)是從始點1到h的邊數≤t-1的最短路徑，因此命題成立.

情形2 如果dt(j)=dt-1(j)，說明在從始點1到h(h≠j)的邊數≤t-1的最短路徑的基礎上增加邊(h，j)新形成的路徑均不優于從始點1到j的邊數≤t-1的最短路徑，這樣一來從始點1到j的邊數≤t-1的最短路徑就是從始點1到j的邊數≤t的最短路徑，命題仍然成立.

綜合上述兩種情形，命題對于k=t時也成立，從而定理1正確.

應用定理1，只需把經典Bellman-Ford算法的迭代數限定為k，就可解決限制邊數≤k的最短路問題.

2 經典Bellman-Ford算法的改進

盡管精簡形式的經典Bellman-Ford算法已經具有較高的計算效率，但距離標號的數目最多可達到n2個.相對于常見形式的Bellman-Ford算法，又增加了集合Ak，這將進一步增加算法的存儲空間.針對上述兩點，本文將得到新的改進算法.

定義d0(i)為上次迭代后點i的距離標號，同時定義集合A為上輪迭代中距離標號變小的點的集合.本文給出第1個改進算法為:

Step 1 初始化.另d(1)=0，d(i)=+∞，(2≤i≤n)，把所有點加入集合A.

Step 2 在第k次迭代中，按照進入順序對集合A中的各點i進行計算為

如果d(j)＜d0(j)，且當點j?B時，把點j加入集合B.

Step 3 如果集合B=?，則算法結束，d(i)就是從點1～i的最短距離;當集合B≠?，且k=n-1時，可判定存在負循環，算法結束;當集合B≠?，且k＜n-1時，執行Step 4.

Step 4 清空集合A，并把集合B中的元素按先進先出順序轉到集合A，再清空集合B，同時對任意的點i(1≤i≤n)，令

再令k=k+1，轉到Step 2.

對照精簡形式的算法，第1改進算法用集合A代替了精簡形式中的Ak(1≤k≤n-1).另外，第1改進算法中，僅僅使用了距離標號d0(i)和d(i)，(1≤i≤n)，而精簡形式一般要使用至少n2個距離標號.因而，第1改進算法顯著提高了存儲效率.

上述改進算法事實上借鑒了劃分算法的思想，也就是參與第k次迭代計算的點放在集合A中，而把參加第k+1次迭代計算的點放在集合B中.但二者也有根本的區別，主要區別在于劃分算法根本沒有用到上一輪的距離標號d0(i)，僅僅使用了距離標號d(i).為了顯示這個區別，特給出以下劃分算法作出比較.

Step 1 初始化.令d(1)=0，d(i)=+∞，(2≤i≤n)，把所有點加入集合A.

Step 2 在第k次迭代中，按照進入順序對集合A中的各點i進行計算為

如果d(j)＜d0(j)，則當j∈A且j?B時，把點j加入集合B;而當j?A時，把點j加入集合A.

Step 3 如果集合B=?，則算法結束，d(i)就是從點1到i的最短距離;當集合B≠?，且k=n-1時，可判定存在負循環，算法結束;當集合B≠?，且k＜n-1時，執行Step 4.

Step 4 清空集合A，并把集合B中的元素按進入順序轉到集合A，再清空集合B，同時對任意的點i(1≤i≤n)，令

再令k=k+1，轉到Step 2.

本文提出的第1個改進算法盡管減少了算法的存儲空間，但算法仍可以進一步改進，也就是可減少Step 4的計算量，進一步改進算法(第2改進算法)為:

Step 1 初始化.另d(1)=0，d(i)=+∞，(2≤i≤n)，把所有點加入集合A.

Step 2 具有兩種情形:

情形1 在第t=2k-1(k≥1)次迭代中，按照進入順序對集合A中的各點i進行計算為

如果d(j)＜d0(j)，當點j?B時，把點j加入集合B.

把點i從集合A中移除.

情形2 在第t=2k(k≥1)次迭代中，按照進入順序對集合B中的各點i進行計算為

如果d(j)＜d0(j)，且當點j?A時，把點j加入集合A.

把點i從集合B中移除.

Step 3 也分兩種情形:

情形1 在奇數次迭代中，如果集合B=?，則算法結束，d(i)就是從點1到i的最短距離;當集合B≠?，且t=n-1時，可判定存在負循環，算法結束;當集合B≠?，且t＜n-1時，執行Step 4.

情形2 在偶數次迭代中，如果集合A=?，則算法結束，d(i)就是從點1到i的最短距離;當集合A≠?，且t=n-1時，可判定存在負循環，算法結束;當集合A≠?，且k＜n-1時，執行Step 4.

Step 4 對任意的點i(1≤i≤n)，令

再令t=t+1，轉到Step 2.

比較本文提出的兩個改進算法，可看出第2個改進算法減少了把集合B的元素轉移到集合A、再清空集合B這個環節所發生的計算量.

關于簡化算法和兩個改進算法均滿足下列結論:

定理2 對于同一個最短路問題，如果3個算法(經典Bellman-Ford算法的精簡形式、第1改進算法和第2改進算法)的初始距離標號是相同的，那么3個算法不僅具有相同的迭代次數，而且每一次迭代后距離標號改變的點形成的集合也是相同的.

證 明 在經典Bellman-Ford算法的常見形式中，在每一次迭代中每一條邊都要參與計算.如果在第k次迭代后，點i的距離標號沒有改變，那么點i的關聯邊(i，j)不會影響點j在k+1次迭代后的距離標號，因而只考慮在第k次迭代后距離標號變化的點u的關聯邊(u，v)，這樣就形成了經典Bellman-Ford算法的精簡形式.而兩個改進算法與精簡形式的區別僅僅表現為實現方法上的不同.因而，這3個算法必然具有相同的迭代次數，且每一次迭代后距離標號改變的點形成的集合也是相同的.

盡管由經典Bellman-Ford算法的精簡形式推廣到第1改進算法應該是非常自然的，但與第1改進算法相類似的算法形式尚未在相關文獻發現.究其原因，可能是劃分算法的提出造成了經典Bellman-Ford算法在計算效率方面的劣勢，因而對它的研究鮮有關注.

3 算法實驗及評估

由于只有經典Bellman-Ford算法的常見形式、第1改進算法和第2改進算法可解決有邊數限制最短路問題，而其他已有的改進算法(如劃分算法)均不適用，因而只對上述3個算法進行實驗和評估.3個算法測試用的有向圖均為完全圖，均使用同樣的例子進行測試，實驗規模分別取點數 n 為 100、200、500、1 000、2 000、3 000、5 000、6 000和8 000等9個規模水平.有向圖的權重服從均勻分布，可取1～100 000之間的任一整數.圖結構采用矩陣描述.由于3個算法具有相同的迭代步數，因而算法試驗以求得最短路徑的迭代步數為參考標準.實驗用的計算機為聯想ThinkPad筆 記 本，CPU 為 Inteli5-2410M 2.30 GHz，內存為2.0 G.每一個規模水平分別測試1 000個隨機生成的例子.實驗結果如表1所示.

表1 經典Bellman-Ford算法3種實現形式的計算時間ms

根據上述實驗數據，可以得到:

1)第2改進算法在規模 ＜6 000以內具有絕對的優勢，但僅僅略優于第1改進算法.相對于第1改進算法，第2改進算法主要是減少了把集合B的元素轉移到集合A、再清空集合B這個環節，因而可提高計算效率，這一點通過實驗數據得以證實.而規模 ＞6 000后，反而第1改進算法占有優勢.

2)經典Bellman-Ford算法的常見形式確實需要更多的計算量，兩個改進算法在規模≥6000個點時，計算效率提高了近30倍.

4 結論

1)對經典Bellman-Ford算法進行了改進，得到兩個改進算法.這兩個改進算法可高效地求解有邊數限制的最短路問題.算法實驗表明，兩個改進算法計算效率顯著，在規模≥6 000個點時比經典Bellman-Ford算法快大約30倍.

2)盡管文獻［1］宣稱可改進算法的實現形式以提高計算效率，但已有改進算法均不適用于有邊數限制最短路問題，這決定了兩個改進算法是經典Bellman-Ford算法的全新改進，將使得Bellman-Ford算法在解決有邊數限制的最短路問題上更具競爭力.

［1］BELLMAN R E.On a routing problem［J］.Quarterly of Applied Mathematics，1958，16(1):87 －90.

［2］LEWANDDOWSKI S.Shortest paths and negative cycle detection in graphs with negative weights［R］.Technical Report，Stuttgart University，2010.

［3］韓偉一，王錚.負權最短路問題的新算法［J］.運籌學學報，2007，11(1):111－120.

［4］CHERKASSKY B V，GEORGIADIS L，GOLDBERG A V，et al.Shortest-path feasibility algorithm:an experimental evaluation［J］.ACM Journal of Experimental Algorithmics，2009，14(7):1 －37.

［5］GLOVER F，KLINGMAN D，PHILLIPS N V.A new polynomially bounded shortest path algorithm［J］.Operations Research，1985，33(1):65－72.

［6］GLOVER F，KLINGMAN D，PHILLIPS N V，et al.New polynomial shortest path algorithms and its computational attributes［J］.Management Science，1986，31(9):1106－1128.

［7］HUNG M S，DIVOKY J J.A computational study of efficient shortest path algorithms［J］.Computer ＆ Operations Research，1988，15(6):567 －576.

［8］AHUJA R K，MAGNANTI K，ORLIN J B.Network Flows-theory，algorithm，and applications［M］.New Jersey:Prentice Hall，Englewood Cliffs，1993.

［9］孫強，楊宗源.求受頂點數限制的最短路徑問題的一個算法［J］.計算機工程，2002，28(9):73－74.

［10］SAIGAL R.A constrained shortest path route problem［J］.Operations Research，1968，16:205 －209.

［11］CHERKASSKY B V，GOLDBERG A V.Negative-cycle detection algorithm［C］//Proceedings of the Fourth Annual European Symposium on Algorithms.London，UK:Springer-Verlag，1996:349－363.

Improvement and experimental evaluation on classical Bellman-Ford algorithm

HAN Wei-yi
(School of Economic and Management，Harbin Institute of Technology，150001 Harbin，China)

Classical Bellman-Ford algorithm is improved to solve the shortest path problem with bounded edge number efficiently.Using the experience of partitioning algorithm for reference，two improved algorithms are obtained，which can decrease the number of distance labels of vertices.Since all existing improved Bellman-Ford algorithms can’t solve the shortest path problem with bounded edge number，these two improved algorithms are entirely new.In contrast to the common version of Bellman-Ford algorithm，these two improved algorithms can save storage space efficiently，and can raise computing efficiency remarkably.

algorithm;Bellman-Ford algorithm;partitioning algorithm;the shortest path problem

TP301.6

A

0367－6234(2012)07－0074－04

2012－04－01.

國家自然科學基金資助項目(70672063);哈爾濱工業大學青年優秀基金資助項目(2009036).

韓偉一(1974—)，男，博士，講師.

韓偉一，wyhan@mails.gucas.ac.cn.

(編輯 張 紅)