固定序Bellman?Ford算法的一個改進(jìn)

韓偉一

（哈爾濱工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院，150001哈爾濱）

固定序Bellman?Ford算法的一個改進(jìn)

韓偉一

（哈爾濱工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院，150001哈爾濱）

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

算法；Bellman?Ford算法；先進(jìn)先出；固定序；最短路問題

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

1 固定序算法及其修正

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

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

Step 2 在第h次迭代中，按照編號順序?qū)中的各點i進(jìn)行計算

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

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

Step 4 令h＝h＋1，轉(zhuǎn)到Step 2.

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

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

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

Step 2 在第h次迭代中，按照編號順序?qū)中的各點i進(jìn)行計算

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

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

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

再令h＝h＋1，轉(zhuǎn)到Step 2.

2 修正的先進(jìn)先出算法

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

修正的先進(jìn)先出算法仍然采用相應(yīng)固定序算法的問題描述和符號，算法如下：

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

Step 2 在第h次迭代中，按照進(jìn)入順序?qū)中的各點i進(jìn)行計算

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

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

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

再令h＝h＋1，轉(zhuǎn)到Step 2.

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

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

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

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

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

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

證明 參見文獻(xiàn)［2］的定理1.

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

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

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

3 算法的實驗評估

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

3.1 稀疏程度和計算規(guī)模的影響實驗

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

本文同時選擇了12類規(guī)模水平進(jìn)行試驗評估，其中小規(guī)模水平（點數(shù)＜10 000的圖）4種、中規(guī)模水平（點數(shù)介于10 000～100 000的圖）4種、大規(guī)模水平（點數(shù)＞100 000的圖）4種．k取值為n／4．之所以設(shè)定最短路徑中的邊數(shù)上限k為n／4，主要是保證盡可能多的迭代次數(shù)．相關(guān)評估結(jié)果如表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

根據(jù)表1～12的實驗數(shù)據(jù)，可得如下結(jié)論：

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

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

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

3.2 k的影響實驗

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

根據(jù)表13～16，可得如下結(jié)論：

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

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

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

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

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

表15 修正的先進(jìn)先出算法與修正的固定序算法計算時間之比

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

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

4 結(jié) 論

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

2）在大規(guī)模情形下，相對于文獻(xiàn)［2］提出的修正的先進(jìn)先出算法，修正的固定序算法相對簡單、易于實現(xiàn)，實驗表明它具有顯著的競爭優(yōu)勢，僅僅在少數(shù)情形下處于落后狀態(tài).

［1］韓偉一，王錚.負(fù)權(quán)最短路問題的新算法［J］.運籌學(xué)學(xué)報，2007，11（1）：111-120.

［2］韓偉一.經(jīng)典Bellman-Ford算法的改進(jìn)及其實驗評估［J］.哈爾濱工業(yè)大學(xué)學(xué)報，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］段凡丁.關(guān)于最短路徑的SPFA快速算法［J］.西南交通大學(xué)學(xué)報，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.

國家自然科學(xué)基金（71101037）；中央高?；究蒲袠I(yè)務(wù)費專項資金（HIT.HSS.201406）.

韓偉一（1974—），男，講師，碩士生導(dǎo)師.

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