經(jīng)典Bellman-Ford算法的改進(jìn)及其實(shí)驗(yàn)評(píng)估

韓偉一

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

經(jīng)典Bellman-Ford算法的改進(jìn)及其實(shí)驗(yàn)評(píng)估

韓偉一

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

針對(duì)以高效求解有邊數(shù)限制的最短路問題，對(duì)經(jīng)典Bellman-Ford算法進(jìn)行了改進(jìn).借鑒劃分算法的思想，通過減少距離標(biāo)號(hào)的數(shù)目，得到了兩個(gè)改進(jìn)算法.既然已有的改進(jìn)算法均不能解決有邊數(shù)限制的最短路問題，因而本算法是經(jīng)典Bellman-Ford算法的全新改進(jìn).相對(duì)于經(jīng)典Bellman-Ford算法，改進(jìn)后的算法不僅可有效地節(jié)省存儲(chǔ)空間，而且實(shí)驗(yàn)表明能顯著地提高計(jì)算效率.

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

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

1 經(jīng)典Bellman-Ford算法的兩種形式及其性質(zhì)

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

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

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

Step 3 當(dāng)所有的點(diǎn)i(1≤i≤n)均滿足dt-1(i)=dt(i)，(t≤n)時(shí)，dt(i)就是從點(diǎn)1到i的最短距離;當(dāng)存在某個(gè)點(diǎn)j滿足dn-1(j)≠dn(j)時(shí)，可判定存在負(fù)循環(huán)，算法結(jié)束.

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

定義Ak為在第k-1輪迭代中距離標(biāo)號(hào)減少的點(diǎn)的集合，則經(jīng)典Bellman-Ford算法又可采取下列精簡形式為:

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

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

Step 3 按照進(jìn)入順序?qū)k中的各點(diǎn)i進(jìn)行計(jì)算為

如果dk(j)＜dk-1(j)，且當(dāng)點(diǎn)j?B時(shí)，則把點(diǎn)j加入集合Ak+1.

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

Step 5 令k=k+1，轉(zhuǎn)到Step 2.

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

經(jīng)典Bellman-Ford算法無論采用上述哪種形式，都具有以下性質(zhì):

性質(zhì)1 算法的迭代次數(shù)為最短路徑樹的深度.

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

性質(zhì)3 算法的最壞計(jì)算復(fù)雜性為O(nm).

性質(zhì)4 算法經(jīng)過n-1次迭代后就可判定負(fù)循環(huán)的存在.

上述4個(gè)性質(zhì)已經(jīng)由相關(guān)文獻(xiàn)證實(shí)，本文不給出具體證明.但針對(duì)性質(zhì)1將給出以下結(jié)論:

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

證明 用數(shù)學(xué)歸納法證明，顯然k=1時(shí)，命題成立.

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

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

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

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

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

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

2 經(jīng)典Bellman-Ford算法的改進(jìn)

盡管精簡形式的經(jīng)典Bellman-Ford算法已經(jīng)具有較高的計(jì)算效率，但距離標(biāo)號(hào)的數(shù)目最多可達(dá)到n2個(gè).相對(duì)于常見形式的Bellman-Ford算法，又增加了集合Ak，這將進(jìn)一步增加算法的存儲(chǔ)空間.針對(duì)上述兩點(diǎn)，本文將得到新的改進(jìn)算法.

定義d0(i)為上次迭代后點(diǎn)i的距離標(biāo)號(hào)，同時(shí)定義集合A為上輪迭代中距離標(biāo)號(hào)變小的點(diǎn)的集合.本文給出第1個(gè)改進(jìn)算法為:

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

Step 2 在第k次迭代中，按照進(jìn)入順序?qū)螦中的各點(diǎn)i進(jìn)行計(jì)算為

如果d(j)＜d0(j)，且當(dāng)點(diǎn)j?B時(shí)，把點(diǎn)j加入集合B.

Step 3 如果集合B=?，則算法結(jié)束，d(i)就是從點(diǎn)1～i的最短距離;當(dāng)集合B≠?，且k=n-1時(shí)，可判定存在負(fù)循環(huán)，算法結(jié)束;當(dāng)集合B≠?，且k＜n-1時(shí)，執(zhí)行Step 4.

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

再令k=k+1，轉(zhuǎn)到Step 2.

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

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

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

Step 2 在第k次迭代中，按照進(jìn)入順序?qū)螦中的各點(diǎn)i進(jìn)行計(jì)算為

如果d(j)＜d0(j)，則當(dāng)j∈A且j?B時(shí)，把點(diǎn)j加入集合B;而當(dāng)j?A時(shí)，把點(diǎn)j加入集合A.

Step 3 如果集合B=?，則算法結(jié)束，d(i)就是從點(diǎn)1到i的最短距離;當(dāng)集合B≠?，且k=n-1時(shí)，可判定存在負(fù)循環(huán)，算法結(jié)束;當(dāng)集合B≠?，且k＜n-1時(shí)，執(zhí)行Step 4.

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

再令k=k+1，轉(zhuǎn)到Step 2.

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

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

Step 2 具有兩種情形:

情形1 在第t=2k-1(k≥1)次迭代中，按照進(jìn)入順序?qū)螦中的各點(diǎn)i進(jìn)行計(jì)算為

如果d(j)＜d0(j)，當(dāng)點(diǎn)j?B時(shí)，把點(diǎn)j加入集合B.

把點(diǎn)i從集合A中移除.

情形2 在第t=2k(k≥1)次迭代中，按照進(jìn)入順序?qū)螧中的各點(diǎn)i進(jìn)行計(jì)算為

如果d(j)＜d0(j)，且當(dāng)點(diǎn)j?A時(shí)，把點(diǎn)j加入集合A.

把點(diǎn)i從集合B中移除.

Step 3 也分兩種情形:

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

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

Step 4 對(duì)任意的點(diǎn)i(1≤i≤n)，令

再令t=t+1，轉(zhuǎn)到Step 2.

比較本文提出的兩個(gè)改進(jìn)算法，可看出第2個(gè)改進(jìn)算法減少了把集合B的元素轉(zhuǎn)移到集合A、再清空集合B這個(gè)環(huán)節(jié)所發(fā)生的計(jì)算量.

關(guān)于簡化算法和兩個(gè)改進(jìn)算法均滿足下列結(jié)論:

定理2 對(duì)于同一個(gè)最短路問題，如果3個(gè)算法(經(jīng)典Bellman-Ford算法的精簡形式、第1改進(jìn)算法和第2改進(jìn)算法)的初始距離標(biāo)號(hào)是相同的，那么3個(gè)算法不僅具有相同的迭代次數(shù)，而且每一次迭代后距離標(biāo)號(hào)改變的點(diǎn)形成的集合也是相同的.

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

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

3 算法實(shí)驗(yàn)及評(píng)估

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

表1 經(jīng)典Bellman-Ford算法3種實(shí)現(xiàn)形式的計(jì)算時(shí)間ms

根據(jù)上述實(shí)驗(yàn)數(shù)據(jù)，可以得到:

1)第2改進(jìn)算法在規(guī)模 ＜6 000以內(nèi)具有絕對(duì)的優(yōu)勢(shì)，但僅僅略優(yōu)于第1改進(jìn)算法.相對(duì)于第1改進(jìn)算法，第2改進(jìn)算法主要是減少了把集合B的元素轉(zhuǎn)移到集合A、再清空集合B這個(gè)環(huán)節(jié)，因而可提高計(jì)算效率，這一點(diǎn)通過實(shí)驗(yàn)數(shù)據(jù)得以證實(shí).而規(guī)模 ＞6 000后，反而第1改進(jìn)算法占有優(yōu)勢(shì).

2)經(jīng)典Bellman-Ford算法的常見形式確實(shí)需要更多的計(jì)算量，兩個(gè)改進(jìn)算法在規(guī)模≥6000個(gè)點(diǎn)時(shí)，計(jì)算效率提高了近30倍.

4 結(jié)論

1)對(duì)經(jīng)典Bellman-Ford算法進(jìn)行了改進(jìn)，得到兩個(gè)改進(jìn)算法.這兩個(gè)改進(jìn)算法可高效地求解有邊數(shù)限制的最短路問題.算法實(shí)驗(yàn)表明，兩個(gè)改進(jìn)算法計(jì)算效率顯著，在規(guī)模≥6 000個(gè)點(diǎn)時(shí)比經(jīng)典Bellman-Ford算法快大約30倍.

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

［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］韓偉一，王錚.負(fù)權(quán)最短路問題的新算法［J］.運(yùn)籌學(xué)學(xué)報(bào)，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］孫強(qiáng)，楊宗源.求受頂點(diǎn)數(shù)限制的最短路徑問題的一個(gè)算法［J］.計(jì)算機(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.

國家自然科學(xué)基金資助項(xiàng)目(70672063);哈爾濱工業(yè)大學(xué)青年優(yōu)秀基金資助項(xiàng)目(2009036).

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

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

(編輯 張 紅)