韓偉一

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

?

基于固定序的Bellman-Ford算法的改進

韓偉一

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

固定序算法是Bellman-Ford算法的一種基本改進算法。為了改變固定序算法在稀疏圖上的劣勢，本文通過預(yù)先訂制參與迭代的點的計算順序，對該算法進行了改進。實驗表明，在稀疏圖上, 改進后的算法相對于原算法計算效率提高了近50%, 并能夠與國際流行的先進先出算法相媲美。本文的工作表明，固定序算法不僅在大規(guī)模稠密圖上具有明顯的優(yōu)勢，而且在稀疏圖上也具有很強的競爭力。

運籌學(xué);固定序改進算法;最短路序;拓撲序Bellman-Ford算法

0 引言

Bellman-Ford算法是解決負權(quán)最短路問題公認的最好算法之一[4,5,10,13], 自1958年提出以來, 共經(jīng)歷了三個發(fā)展階段[1～3]：第一階段，動態(tài)規(guī)劃模式階段, 即原始的Bellman-Ford算法；第二階段，基本改進階段，在第一階段的每次迭代中所有點都要參與計算，而在第二階段中只有在上次迭代中距離標(biāo)號改變的點才參與下一次迭代, 從而使得計算效率顯著提高, 迭代次數(shù)明顯減少；第三階段，加速技術(shù)階段，主要體現(xiàn)為上次迭代中距離標(biāo)號改變的點并不全部參與下一輪迭代計算，因而還可進一步提高計算效率。第三階段的算法一般以第二階段的算法為基礎(chǔ)，因而第二階段的算法也稱為Bellman-Ford算法的基本改進算法。目前, 主要有5類基本改進算法, 即先進先出算法[10～14]、后進先出算法[14]、Yen算法[8]、快速算法[9]和固定序算法[1,2]等。第三階段的主要工作有1993年Goldberg和Radzik兩人提出的拓撲序技術(shù)[6]，Tarjan于1981年提出的裝配子樹技術(shù)[7]，以及1985年Glover等人提出的門檻技術(shù)等[4,5], 1996年Cherkassky等人提出的父點技術(shù)[10,14]等。文獻[2]提出的固定序算法是一種基本改進算法，它的特點是每次迭代過程中參與計算的點總遵照固定的順序。由于每一次迭代參與的點和點數(shù)是不確定的，因而主流的算法采用了先進先出的順序，即距離標(biāo)號先改變的點先參與迭代計算，本文稱之為先進先出算法(FIFO Algorithm)。先進先出算法是當(dāng)前最具影響力的一種基本改進算法。鑒于基本改進算法是第三階段算法的基礎(chǔ)，本文將開展兩方面的工作：(1)通過實驗說明固定序算法在稠密圖上有明顯的競爭優(yōu)勢; (2) 借鑒拓撲序技術(shù)對固定序算法作進一步的改進, 并通過實驗說明該算法在稀疏圖上能夠與先進先出算法相媲美。

1 固定序算法及其實驗性能

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

Step 1 初始化。令d(1)=0，d(i)=+∞(2≤i≤n)，把點1加入集合A。k表示迭代次數(shù)，賦初值為1。

Step 2 在第k次迭代中，按照編號順序?qū)中的各點i進行如下計算

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

Step 3 如果集合A為空集，則算法結(jié)束，d(i)就是從點1到點i的最短距離；當(dāng)集合A非空，且k=n-1時，可判定存在負循環(huán)，算法結(jié)束；當(dāng)集合A非空時，且k

Step 4 令k=k+1，轉(zhuǎn)到Step 2。

在第一階段，采用固定序是非常自然的，在第二階段采用固定序是不明智的，原因有兩點：(1)它需要把參與迭代計算的點按既定順序進行排序，增加了額外的計算時間；(2)一成不變的計算順序使得算法缺乏靈活性，可能會導(dǎo)致算法的低效率。因而，在第二階段和第三階段固定序算法鮮有文獻提及。為了克服這一缺點，我們使用了一種簡單的技術(shù)，即對所有點按給定的順序逐個檢查，如果距離標(biāo)號改變了就參與計算，否則就不參與，這樣可保證參與迭代點的順序，但增加了距離標(biāo)號未改變的點的檢查工作。然而，這種理論上顯得較弱的算法，在使用鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)時，卻極具有競爭力，在稠密圖上, 它比主流的先進先出算法具有更加卓越的計算效率。為了驗證這一優(yōu)勢，本文通過實驗對兩個算法進行了比較。在實驗中，兩種算法都選擇了各自最有利的數(shù)據(jù)結(jié)構(gòu)，先進先出算法使用壓縮鄰接表(也稱為鄰接順序表)，固定序算法使用鄰接矩陣。同時，選擇了6000點、8000點和10000點三種規(guī)模下的4種不同稀疏程度進行實驗。沿用文獻[2]的定義，用邊數(shù)與點數(shù)之比來表示圖的稀疏程度。實驗用的有向圖的權(quán)重服從均勻分布，可取1到100000之間的任一整數(shù)。為了保證實驗結(jié)果的可靠性，每種情形將實驗10000個例子。所用的計算機為聯(lián)想ThinkPad筆記本，CPU為Intel i5-2410M 2.30GHz, 內(nèi)存為2.0G。算法的比較都使用相同的例子。算法程序均采用結(jié)構(gòu)化語言Pascal。相關(guān)的實驗結(jié)果，見表1、表2和表3：

表1 10000個點下固定序算法與先進先出序算法的比較

由表1、表2和表3可以看出，在點數(shù)相同的情況下，先進先出的算法隨著稀疏程度的降低計算時間不斷下降, 而固定序算法的計算時間變化幅度不大, 竟然會出現(xiàn)不降反升的現(xiàn)象。之所以出現(xiàn)如上現(xiàn)象, 根本原因在于固定序算法采用的數(shù)據(jù)結(jié)構(gòu)為鄰接矩陣, 而先進先出算法采用的數(shù)據(jù)結(jié)構(gòu)為壓縮鄰接表，鄰接矩陣將使所有問題只能以完全圖的形式參與計算，也就是兩點i和j之間如果無邊存在，則添加邊(i,j), 且令權(quán)重為+∞，最終把一個非完全圖構(gòu)造為完全圖。另外，由于所計算的問題均是隨機形成的，因而出現(xiàn)不降反升的現(xiàn)象是正常的，但兩個算法的計算時間比所體現(xiàn)的關(guān)系卻是相對穩(wěn)定的。

表2 8000個點下固定序算法與先進先出序算法的比較

表3 6000個點下固定序算法與先進先出序算法的比較

綜合表1、表2和表3的實驗結(jié)果，可得出如下幾點結(jié)論：(1)在稠密圖上，固定序算法確實比主流的先進先出序算法有明顯的競爭優(yōu)勢；(2)固定序算法的競爭優(yōu)勢將隨著點數(shù)規(guī)模的增加和稀疏程度的增大愈加明顯, 在6000個點的完全圖上, 固定序算法僅比先進先出序算法快1.3倍, 而在10000個點的完全圖上效率提高了40%；(3)固定序的計算效率，還將隨著稀疏程度的增大愈加顯著，在10000個點的規(guī)模下，稀疏程度為7000時, 固定序算法的計算效率稍弱于先進先出算法，但當(dāng)稀疏程度增加到7500時, 情況就有了明顯改觀；(4)固定序的優(yōu)勢范圍將隨著點數(shù)規(guī)模的增加而進一步擴大，在6000個點時，稀疏程度達到點數(shù)的5/6, 固定序算法才可以勝過先進先出算法, 但當(dāng)規(guī)模升到10000個點時, 稀疏程度只需達到點數(shù)的3/4就可以。

盡管固定序算法在稠密圖上顯示出了明顯的競爭優(yōu)勢，但也存在明顯的劣勢：(1)它的競爭優(yōu)勢得益于所采用的數(shù)據(jù)結(jié)構(gòu)——鄰接矩陣，而壓縮鄰接表是稀疏圖上最常用、最有競爭力的數(shù)據(jù)結(jié)構(gòu)；(2)固定序算法在稀疏圖上不具有優(yōu)勢，后文表4～6的實驗結(jié)果已經(jīng)表明，兩個算法都采用壓縮鄰接表的數(shù)據(jù)結(jié)構(gòu)，在規(guī)模為10000個點、稀疏程度分別為5、10、15和20時，先進先出算法比固定序算法計算效率大約快50%。

2 固定序算法的改進

為了改變固定序算法在稀疏圖上的劣勢，可從兩方面對算法進行改進：第一，對參與迭代的點的順序進行預(yù)先訂制；第二，在算法的初始化階段, 對參與迭代的點進行排序。第一個改進有一定的現(xiàn)實依據(jù)，因為計算工作都是把預(yù)先處理好的數(shù)據(jù)交給算法的。然而，預(yù)先排序會增加額外的計算時間，無法真實體現(xiàn)一個算法的真實競爭力，因而第二個改進更加合理一點。算法的改進也采用壓縮鄰接表的數(shù)據(jù)結(jié)構(gòu)。

之所以改進參與迭代的點的順序，其理論來源來自于拓撲序。拓撲序是針對無循環(huán)的有向圖提出的，指對各點進行排序后，如果點i的位置先于點j，那么有向圖中一定不存在邊(j,i)。關(guān)于拓撲序有如下的定理：

定理1 如果圖G(V,E)為無循環(huán)的有向圖，那么Bellman-Ford算法第二階段及以后的各種改進算法如果按照拓撲序?qū)Ω鼽c進行迭代計算，算法可以在O(m)的時間內(nèi)獲得從源點到各點的最短路徑，而且僅需迭代一次。

遺憾的是，有循環(huán)的有向圖卻不存在拓撲序，只有無循環(huán)的有向圖才存在拓撲序。值得指出的是，Bellman-Ford算法及其改進算法的計算結(jié)果將得到最短路徑樹，而最短路徑樹是無循環(huán)的有向圖。為了方便論述，本文提出如下定義：

定義1 最短路徑樹是有向圖的特殊子圖，由它得到的拓撲序特稱為最短路序。

顯然，最短路序是拓撲序概念的一個推廣，不僅無循環(huán)的有向圖存在最短路序，而且有循環(huán)的有向圖也存在最短路序。關(guān)于最短路序，也有如下定理：

定理2 如果圖G(V,E)為有向圖，那么固定序算法按照最短路序?qū)Ω鼽c進行迭代計算，算法可以在O(m)的時間內(nèi)獲得從源點到各點的最短路徑，而且僅需迭代一次。

證明 如果P是從始點1到點t的最短路徑，即1→t1→t2→…→tk→t,為了方便論述，用t0來表示點1, 用tk+1來表示點t。如果按照最短路序進行計算，那么點ts必定先于點ts+1參與計算。根據(jù)固定序算法的Step 2，在第一次迭代中，ts(0≤s≤k)將使得ts+1進入集合A, 這樣不僅保證了參與計算的順序，還同時保證了ts和ts+1都能參與計算，而計算結(jié)果又使得d(ts+1)=d(ts)+w(ts,ts+1)，這意味著經(jīng)過第一輪迭代就可求得從點1到點t的最短路徑。鑒于點t的任意性，因而在第一輪迭代中，所有點都參與了迭代計算，并且都得到了最短路。因為每個點僅參與迭代計算一次，因而每邊最多只能參加一次迭代，故算法的復(fù)雜性為O(m)。命題得證。

定理2很容易推廣到Bellman-Ford算法第二階段及以后的其它改進算法上。盡管最短路序有如此優(yōu)良的理論性質(zhì)，但事先很難預(yù)知，只能合理加以借鑒。既然事先很難得到最短路序，可以考慮近似最短路序，保證盡量多的點滿足最短路序，同時允許部分點不滿足最短路序。在近似最短路序中，無疑滿足最短路序的點越多，算法的效率自然就越高。根據(jù)這個想法，可對固定序算法改進如下：

Step 1 初始化。令d(1)=0，d(i)=+∞(2≤i≤n)，把點1加入集合A，同時訂制近似最短路序的第一個點，即點1。k表示迭代次數(shù)，賦初值為1。

Step 2 在第1次迭代中，按照訂制的順序?qū)χ械母鼽c進行如下計算

如果d(j)變小，則當(dāng)j?A時, 把點j加入集合A。若d(j)變小且原值為+∞，設(shè)最短路序中已有t個點，那么就把點j作為第t+1個點。當(dāng)所有進入A的點都參與計算后，則轉(zhuǎn)入步驟Step 4。

Step 3 在第k(k≥2)次迭代中，按照訂制的順序?qū)中的各點i進行如下計算

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

Step 4 如果集合A為空集，則算法結(jié)束，d(i)就是從點1到點i的最短距離；當(dāng)集合A非空，且k=n-1時，可判定存在負循環(huán)，算法結(jié)束；當(dāng)集合A非空，且k

Step 5 令k=k+1，轉(zhuǎn)到Step 3。

盡管步驟Step 2對點進行排序的工作稍顯簡單，但卻體現(xiàn)出了較高的計算效率，采用較復(fù)雜的技巧反而會減慢計算速度，究其原因在于參與迭代計算的點數(shù)盡管減少了，但額外增加了更多的排序時間。

3 實驗測試

為了測試改進后的算法效率，特選擇了壓縮鄰接表, 這個最為常用的數(shù)據(jù)結(jié)構(gòu)對固定序算法來說是最不利的，但對于先進先出算法來說卻是最有利的數(shù)據(jù)結(jié)構(gòu)。實驗分別選擇了6000點、8000點和10000點三種規(guī)模下的4種不同稀疏程度，選擇了先進先出算法和原始的固定序算法進行比較，仍采用前文的實驗方法。相關(guān)的實驗結(jié)果，見表4、表5和表6：

表4 6000個點下改進固定序算法的績效實驗

表5 8000個點下改進固定序算法的績效實驗

表6 10000個點下改進固定序算法的績效實驗

綜合表4、表5和表6的實驗結(jié)果，可得出如下幾點結(jié)論：(1)在稀疏程度小于10時，改進后的固定序算法已經(jīng)略勝于先進先出算法；(2)當(dāng)稀疏程度大于10時，競爭優(yōu)勢被先進先出算法所取代，而且隨著稀疏程度的增大計算優(yōu)勢將逐步喪失；(3)改進后的固定序算法相對于原算法，效率有了顯著提高，大約提高了近50%。鑒于現(xiàn)實中所面臨的圖絕大多數(shù)為稀疏程度小于10的稀疏圖，因而改進后的固定序算法在稀疏圖上是一種真正具有競爭力的算法。

盡管改進后的固定序算法在稀疏程度不大于10的有向圖上有競爭優(yōu)勢，但本文的實驗表明：在采用壓縮鄰接表的數(shù)據(jù)結(jié)構(gòu)時，隨著稀疏程度的增大，固定序算法及其改進算法劣勢將漸趨明顯。

4 結(jié)論

本文主要有三方面的貢獻：(1)驗證了固定序算法在稠密圖上的優(yōu)勢，同時對該算法的優(yōu)勢范圍進行了實驗評估；(2)拓展了拓撲序的概念，提出了最短路序這個適應(yīng)性更強的新概念；(3)通過預(yù)先訂制參與迭代點的順序，改進了固定序算法。改進后的算法能極大地提高固定序算法在稀疏圖上的計算效率，可提高大約50%。相對于國際流行的先進先出算法，改進后的固定序算法在稀疏程度不大于10的有向圖上也取得了競爭優(yōu)勢，這使得固定序算法可成為解決實際問題有競爭力的算法。

在Bellman-Ford算法發(fā)展的第二階段，固定序算法很少引起國際學(xué)術(shù)界的重視。本文對這個算法的優(yōu)勢重新進行了挖掘，使之既可在大規(guī)模稠密圖上有較大范圍的競爭優(yōu)勢，又可在稀疏程度小于20的稀疏圖上與國際流行的先進先出算法相媲美。如何進一步改進固定序算法，使之采用壓縮鄰接表的數(shù)據(jù)結(jié)構(gòu)能獲得更大范圍的競爭優(yōu)勢，使之在更多新領(lǐng)域具有無可比擬的競爭優(yōu)勢，將作為下一步的研究工作。

[1] 韓偉一,王錚.負權(quán)最短路問題的新算法[J].運籌學(xué)學(xué)報,2007,11(1):111-120.

[2] 韓偉一.經(jīng)典Bellman-Ford算法的改進及其實驗評估[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] Glover F, Klingman D, Phillips N V. A new polynomially bounded shortest path algorithm[J]. Operations research,1985, 33(1): 65-72.

[5] Glover F, Klingman D, Phillips N V, Schneider R F. New polynomial shortest path algorithms and its computational attributes[J]. Management science, 1986, 31: 1106-1128.

[6] Goldberg A V, Radzik T. A heuristic improvement of the bellman-ford algorithm[J]. Applied Mathematics letters,1993, 6(3): 3- 6.

[7] Tarjan R E. Shortest paths[R]. AT&T Bell Laboratories, Murray Hill, 1981.

[8] 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.

[9] 段凡丁.關(guān)于最短路徑的SPFA快速算法[J].西南交通大學(xué)學(xué)報,1994,29(2):202-212.

[10] Cherkassky B V, Georgiadis L, Goldberg A V, Tarjan R E, Werneck R F. Shortest-path feasibility algorithm: an experimental evaluation[J]. ACM Journal of experimental algorithmics, 2009, 14(2.7): 1-37.

[11] Hung M S, Divoky J J. A computational study of efficient shortest path algorithms[J]. Computer & Operations research, 1988, 15(6): 567-576.

[12] Lewanddowski S. Shortest paths and negative cycle detection in graphs with negative weights[R]. Stuttgart University, 2010.

[13] Cherkassky B V, Goldberg A V. Negative-cycle detection algorithm[J]. Mathematical programming, 1999, 85: 277-311.

[14] Cherkassky B V, Goldberg A V. Shortest paths algorithms: theory and experimental evaluation[J]. Mathematical programming, 1996, 73: 129-174.

Improvement of Bellman-Ford Algorithm Based on the Fixed Order

HAN Wei-yi

(SchoolofEconomicandManagement,HarbinInstituteofTechnology,Harbin150001,China)

The fixed order algorithm is one of basic improved algorithms on the classic Bellman-Ford algorithm. In view of its inferiority in the sparse directed graph, the algorithm is improved by presenting the computational order of vertices in advance. The experiments show that the improved algorithm is faster than the original one by 50% in the sparse directed graph approximately. Moreover, it is compared with the FIFO algorithm, which is the most attractive basic improved algorithm of Bellman-Ford algorithm at present. It means that the fixed order algorithm is very competitive in both the large-scale dense directed graph and the sparse directed graph.

operations research; improved fixed order algorithm; the shortest path order; topological order; bellman-ford algorithm

2013- 06-27

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

韓偉一(1974-),男,講師，碩士生導(dǎo)師。

O221.7

A

1007-3221(2015)04- 0111- 05