固定序Bellman?Ford算法的一個改進

韓偉一

（哈爾濱工業大學經濟與管理學院，150001哈爾濱）

固定序Bellman?Ford算法的一個改進

韓偉一

（哈爾濱工業大學經濟與管理學院，150001哈爾濱）

通過對固定序Bellman?Ford算法進行修正，獲得了一種求解邊數不大于k的最短路問題的新算法．相對于原始算法，修正后的算法通過改變點的標號過程，使得在第k次迭代后每一條路徑的邊數均不超過k．新算法被證明是正確的，它的計算復雜性為O（km）．實驗表明，在大規模情形下，相對于修正的先進先出算法，該算法具有顯著的競爭優勢.

算法；Bellman?Ford算法；先進先出；固定序；最短路問題

自1958年以來，Bellman?Ford算法一直被公認為是求解負權最短路問題最好的強多項式算法，它的研究歷程可概括為3個發展階段［1-3］：第1階段，動態規劃模式階段，即原始的Bellman?Ford算法；第2階段，基本改進階段，在第1階段的每次迭代中所有點都要參與計算，而在第2階段中只有在上次迭代中距離標號改變的點才參與下一次迭代，從而使得計算效率顯著提高，迭代次數明顯減少［4-8］；第3階段，加速技術階段，主要體現為上次迭代中距離標號改變的點并不全部參與下一輪迭代計算，因而還可進一步提高計算效率.第3階段的算法一般以第2階段的算法為基礎，因而第2階段的算法也稱為Bellman?Ford算法的基本改進算法.目前，主要有5類基本改進算法，即先進先出算法［4，8］、后進先出算法［8］、Yen算法［9］、快速算法［10］和固定序算法［1-2］等.第3階段的主要工作有1993年Goldberg等［11］提出的拓撲序技術，1981年Tarjan［12］提出的裝配子樹技術，以及1985年Glover等［13-14］提出的門檻技術等，1996年Cherkassky等［4，8］提出的父點技術等.需要指出的是，盡管第2、3階段的算法都具有很高的效率，但由于最短路徑中的邊數可能會多于k條，因而均不能解決邊數不大于k的最短路問題（或邊數≤k的最短路問題），為此文獻［2］對先進先出算法進行了修正．本文將對固定序算法進行修正，使得修正后的算法能夠解決有邊數限制的最短路問題，并將該算法與已有的先進先出算法進行比較，用實驗說明它在大規模情形下具有顯著的競爭優勢．

1 固定序算法及其修正

對于一個具有n個點、m條邊的有向圖G（V，E），n個點分別編號為1，2，…，n，且規定點1為源點，用w（i，j）表示有向邊（i，j）的權．定義d（i）為點i的距離標號，h為迭代次數．固定序算法如下：

Step 1 初始化.令d（1）＝0，d（i）＝＋∞，2≤i≤n．把點1加入集合A．對h賦值為1．

Step 2 在第h次迭代中，按照編號順序對A中的各點i進行計算

如果d（j）變小，則當j?A時，把點j加入集合A．從集合A中去除點i．

Step 3 如果集合A為空集，則算法結束，d（i）就是從點1到點i的最短距離；當集合A非空且h＝n-1時，可判定存在負循環，算法結束；當集合A非空且h＜n-1時，執行Step 4.

Step 4 令h＝h＋1，轉到Step 2.

盡管固定序算法在求解負權最短路問題上具有較高的計算效率，但由于求得的是最短路徑，而最短路徑中可能會多于k條邊，因而它也無法直接求解邊數≤k的最短路問題，必須對它加以修正．

在對固定序算法修正以前，需要引入一些新的定義和符號：1）定義d0（i）為上次迭代完成后點i的距離標號；2）在修正的算法中，定義集合A為上輪迭代中距離標號變小的點的集合，定義集合B為本輪迭代中距離變小的點的集合．修正后的固定序算法如下：

Step 1 初始化.令d（1）＝0，d（i）＝＋∞，2≤i≤n，把點1加入集合A．迭代次數h賦初值為1，則第0次迭代的距離標號分別為

Step 2 在第h次迭代中，按照編號順序對A中的各點i進行計算

如果d（j）＜d0（j），且當點j?B時，把點j加入集合B．從集合A中去除點i．

Step 3 如果集合B為空集或h＝k時，則算法結束，d（i）就是從點1到點i的最短距離；當集合B非空且h＜k時，執行Step 4.

Step 4 清空集合A，并把集合B中的元素轉到集合A，再清空集合B，同時對任意的點i（1≤i≤n），令

再令h＝h＋1，轉到Step 2.

2 修正的先進先出算法

文獻［2］對基于先進先出序的Bellman?Ford算法進行了修正，使之能夠解決邊數不大于k的最短路問題，特稱為修正的先進先出算法.作為Bellman?Ford算法的一種基本改進算法，先進先出算法被公認為是解決負權最短路問題最快、最有影響力的算法，第3階段的加速算法都是以它為基礎進行改進的.在文獻［2］中，修正的先進先出算法不僅可以求解邊數≤k的最短路問題，而且顯示出了卓越的計算效率，相對于原始的Bellman?Ford算法效率可提高近30倍.需要指出的是，原始的Bellman?Ford算法可以求解邊數≤k的最短路問題，但第2、3階段的改進算法均不可以.

修正的先進先出算法仍然采用相應固定序算法的問題描述和符號，算法如下：

Step 1 初始化．令d（1）＝0，d（i）＝＋∞，2≤i≤n，把點1加入集合A．迭代次數h賦初值為1，則第0次迭代的距離標號分別為

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

如果d（j）＜d0（j），且當點j?B時，把點j加入集合B．從集合A中去除點i．

Step 3 如果集合B為空集或h＝k時，則算法結束，d（i）就是從點1到點i的最短距離；當集合B非空且h＜k時，執行Step 4.

Step 4 清空集合A，并把集合B中的元素轉到集合A，再清空集合B，同時對任意的點i（1≤i≤n），令

再令h＝h＋1，轉到Step 2.

需要指出的是，本文對文獻［2］中的修正的先進先出算法的表述錯誤進行了糾正，即把d（j）＝修正為d（j）＝

比較兩種修正算法，可以看出兩種算法僅僅在Step 2有微小的差別，也就是修正的先進先出算法參與計算的點按照先進先出的順序，而修正的固定序算法則按照事先給定的編號順序.兩個算法滿足如下定理.

定理1 對于同一個問題，修正的先進先出算法和修正的固定序算法不僅具有相同的迭代次數，而且每一次迭代使用的集合A和迭代后形成的集合B也是相同的．

證明 兩個算法僅僅在Step 2存在一定的差別，其他步驟都是一樣的.在Step 2中，修正的先進先出算法按照先進先出的順序對A中的點進行計算，而修正的固定序算法按照給定的順序對A中的點進行計算．如果每一次迭代使用的集合A是相同的，而且得到的計算結果也是相同的，那么兩個算法無疑具有同樣的迭代次數．

定理1間接說明，本文的算法確實可以求解邊數≤k的最短路問題．也進一步表明，修正的先進先出算法和修正的固定序算法應該具有同樣的計算復雜度．由文獻［2］，有如下引理．

引理1 算法在k次迭代后，如果d（i）＜＋∞，那么可得到從點1到點i的邊數不大于k的一條最短路徑，這條路徑的長度恰為d（i）．

證明 參見文獻［2］的定理1.

定理2 修正的先進先出算法和修正的固定序算法最壞情形下的計算復雜度為O（km）．

證明 在每次迭代中，由于每一條邊參與Step 2的計算過程最多一次，因而每一次迭代的計算復雜度為O（m）．根據引理1，對于求解邊數≤k的最短路問題，迭代次數不會超過k．因而，兩個算法最壞情形下的計算復雜度為O（km）．

需要指出的是，文中提到的3個階段的Bellman?Ford算法最壞情形下的計算復雜性均為O（nm）．

3 算法的實驗評估

由于修正的先進先出算法、修正的固定序算法兩種算法具有相同的、最壞情形的計算復雜度，因而只能通過實驗來比較兩個算法的計算效率．本文將進行兩個實驗：1）設定最短路徑中的邊數上限k為n／4，對兩種算法在多種稀疏程度、多個規模水平下進行評估，以測試稀疏程度和計算規模兩個因素對兩個算法的影響，這里n為有向圖的點數；2）給定計算規模，針對不同的k對兩種算法進行評估，以測試不同k對算法的影響．實驗所用有向圖的權重服從均勻分布，可取1～100 000之間的任一整數.每種圖實驗10 000個例子.實驗用的計算機為聯想ThinkPad筆記本，CPU為Intel i5-2410M 2.30 GHz，內存為2.0 G.算法的比較都使用相同的例子.算法程序均采用結構化語言Delphi7.0.

3.1 稀疏程度和計算規模的影響實驗

本文用邊數與點數之比來表示圖的稀疏程度.在每種圖中，設計了10、50、200和1 000等4種稀疏情形進行評估，主要原因是它們代表了4種典型的稀疏程度，即：1）當稀疏程度≤10時，一般認為是超稀疏的；2）當稀疏程度≤log n時，一般認為是稀疏的，按照本文的實驗規模，50接近于這個水平；3）當稀疏程度接近于n 時，一般認為是超稠密的，按照本文的實驗規模，1 000接近于超稠密水平，而200可認為是稠密的水平．之所以不選擇更大的稀疏程度進行實驗，根本原因是：如果稠密程度＞2 000時，無法在＞100 000個點的規模水平下開展實驗，將發生內存溢出，不能形成完整的實驗結果以進行對比分析．

本文同時選擇了12類規模水平進行試驗評估，其中小規模水平（點數＜10 000的圖）4種、中規模水平（點數介于10 000～100 000的圖）4種、大規模水平（點數＞100 000的圖）4種．k取值為n／4．之所以設定最短路徑中的邊數上限k為n／4，主要是保證盡可能多的迭代次數．相關評估結果如表1～12所示．

表1 2 000個點下的平均計算時間ms

表2 4 000個點下的平均計算時間ms

表3 6 000個點下的平均計算時間ms

表4 8 000個點下的平均計算時間ms

表5 20 000個點下的平均計算時間ms

表6 40 000個點下的平均計算時間ms

表7 60 000個點下的平均計算時間ms

表8 80 000個點下的平均計算時間ms

表9 120 000個點下的平均計算時間ms

表10 140 000個點下的平均計算時間ms

表11 160 000個點下的平均計算時間ms

表12 180 000個點下的平均計算時間ms

根據表1～12的實驗數據，可得如下結論：

1）相對于修正的先進先出算法，在既定的規模水平下，隨著稀疏程度的增加，修正的固定序算法的競爭優勢將越來越不顯著甚至喪失.如在6 000個點的規模水平下，修正的固定序算法在稀疏程度為10時具有更快的計算效率，但當稀疏程度增加為1 000時卻喪失了競爭優勢.

2）相對于修正的先進先出算法，在既定的稀疏程度下，隨著規模水平的增大，修正的固定序算法的競爭優勢將越來越顯著.如在稀疏程度為10的情形下，當規模水平為2 000個點時，修正的固定序算法比修正的先進先出算法計算效率平均慢60.7%，而當規模水平為180 000個點時，修正的固定序算法反而比修正的先進先出算法計算效率平均快75.6%.

3）相對于修正的先進先出算法，當規模水平足夠大時，在所有的稀疏程度下，修正的固定序算法將具備完全的競爭優勢.如當規模水平＜10 000個點時，修正的固定序算法在4種稀疏程度情形下均處于劣勢，而當規模水平＞80 000個點時，這個算法在所有情形下均贏得了優勢.

3.2 k的影響實驗

首先選擇20 000個點和160 000個點兩個規模水平，k分別取值為5、10、15和n／4進行實驗，如表13～15所示．鑒于k為5、稀疏程度為10時，計算結果出現異常，又增加了兩個規模水平（即60 000個點和100 000個點）進行實驗，以給出穩定的規律，如表16所示．

根據表13～16，可得如下結論：

1）由表15可以看出，修正的固定序算法在大規模情形下具有壓倒性的競爭優勢，16種情形下僅當k為5、稀疏程度為10時弱于修正的先進先出算法．

2）由表15還可以看出，在給定的規模水平和稀疏程度情形下，當k取適當值時對修正的固定序算法非常有利，但當k進一步變大或變小時這種有利現象將減弱或消失．如在規模水平為160 000個點、稀疏程度為10的情形下，k為10時最為有利．

3）由表16可以看出，當k和稀疏程度同時較小時，修正的先進先出算法具有絕對的競爭優勢，并隨著規模的增大優勢愈加突出.需要指出的是，在表16中出現了一個反常值，即計算時間值0.78，但從兩個算法的計算時間比來看，規律是十分明顯的.

表13 20 000個點、不同k下的平均計算時間ms

表14 160 000個點、不同k下的平均計算時間ms

表15 修正的先進先出算法與修正的固定序算法計算時間之比

表16 k為5、稀疏程度為10、不同規模水平下的平均計算時間ms

由上述兩個實驗可以看出，盡管兩個算法具有同樣的計算復雜性，但是在不同參數、稀疏程度和規模水平下卻體現了不同的計算效率.因為兩個算法在Step 2中分別采取了不同的數據結構，其中修正的先進先出算法采用了優先隊列來存儲參與迭代的點，而修正的固定序算法則是逐一判斷各點是否可參與迭代.后者相對簡單，易于實現，又能在大規模情形下體現出明顯的競爭優勢，因而具有一定的理論和實踐價值.

4 結 論

1）本文通過對固定序Bellman?Ford算法進行修正，獲得了一種求解邊數≤k的最短路問題的新算法——修正的固定序算法.

2）在大規模情形下，相對于文獻［2］提出的修正的先進先出算法，修正的固定序算法相對簡單、易于實現，實驗表明它具有顯著的競爭優勢，僅僅在少數情形下處于落后狀態.

［1］韓偉一，王錚.負權最短路問題的新算法［J］.運籌學學報，2007，11（1）：111-120.

［2］韓偉一.經典Bellman-Ford算法的改進及其實驗評估［J］.哈爾濱工業大學學報，2012，44（7）：74-77.

［3］BELLMAN R E.On a routing problem［J］.Quarterly of Applied Mathematics，1958，16（1）：87-90.

［4］CHERKASSKY B V，GEORGIADIS L，GOLDBERG A V，etal.Shortest?pathfeasibilityalgorithm：an experimentalevaluation［J］.ACMJournalof Experimental Algorithmics，2009，14（2）：1-37.

［5］HUNG M S，DIVOKY J J.A computational study of efficient shortest path algorithms［J］.Computer＆Operations Research，1988，15（6）：567-576.

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

［7］CHERKASSKY B V，GOLDBERG A V.Negative?cycle detection algorithm［J］.Mathematical Programming，1999，85（2）：277-311.

［8］CHERKASSKY B V，GOLDBERG A V.Shortest paths algorithms：theory and experimental evaluation［J］. Mathematical Programming，1996，73（2）：129-174.

［9］YEN J Y.An algorithm for finding shortest routes from all source nodes to a given destination in general networks［J］.Quarterly of Applied Mathematics，1970，27：526-530.

［10］段凡丁.關于最短路徑的SPFA快速算法［J］.西南交通大學學報，1994，29（2）：202-212.

［11］GOLDBERG A V，RADZIK T.A heuristic improvement of the Bellman-Ford algorithm［J］.Applied Mathematics Letters，1993，6（3）：3-6.

［12］TARJAN R E.Shortest paths［R］.Murray Hill，NJ：AT＆T Bell Laboratories，1981.

［13］GLOVER F，KLINGMAN D D，PHILLIPS N V.A new polynomially boundedshortestpathalgorithm［J］. Operations Research，1985，33（1）：65-73.

［14］GLOVER F，KLINGMAN D D，PHILLIPS N V，et al. Newpolynomialshortestpathalgorithmsandits computational attributes［J］.ManagementScience，1985，31（9）：1106-1128.

（編輯 張 紅）

An improvement on fixed order Bellman?Ford algorithm

HAN Weiyi

（School of Economic and Management，Harbin Institute of Technology，150001 Harbin，China）

In the paper，Bellman?Ford algorithm with fixed order is modified in order to solve the shortest path problem with not more than k edges.After the k?th iteration，each path must own no more than k edges by modifying the labeling process of the origin algorithm.The modified algorithm proves true and its worst?case complexity is O（km）．In contrast to the modified Bellman?Ford algorithm with FIFO order，experiments show that the algorithm has the significant competitive advantage in the large?scale case.

algorithm；Bellman?Ford algorithm；FIFO order；fixed order；the shortest path problem

TP301.6

：A

：0367-6234（2014）11-0058-06

2004-03-02.

國家自然科學基金（71101037）；中央高校基本科研業務費專項資金（HIT.HSS.201406）.

韓偉一（1974—），男，講師，碩士生導師.

韓偉一，wyhan＠hit.edu.cn.