Bellman-Ford 算法及其優(yōu)化
Bellman-Ford算法與另一個(gè)非常著名的Dijkstra算法一樣，用于求解單源點(diǎn)最短路徑問(wèn)題。Bellman-ford算法除了可求解邊權(quán)均非負(fù)的問(wèn)題外，還可以解決存在負(fù)權(quán)邊的問(wèn)題（意義是什么，好好思考），而Dijkstra算法只能處理邊權(quán)非負(fù)的問(wèn)題，因此 Bellman-Ford算法的適用面要廣泛一些。但是，原始的Bellman-Ford算法時(shí)間復(fù)雜度為 O（VE）,比Dijkstra算法的時(shí)間復(fù)雜度高，所以常常被眾多的大學(xué)算法教科書(shū)所忽略，就連經(jīng)典的《算法導(dǎo)論》也只介紹了基本的Bellman-Ford算法，在國(guó)內(nèi)常見(jiàn)的基本信息學(xué)奧賽教材中也均未提及，因此該算法的知名度與被掌握度都不如Dijkstra算法。事實(shí)上，有多種形式的Bellman-Ford算法的優(yōu)化實(shí)現(xiàn)。這些優(yōu)化實(shí)現(xiàn)在時(shí)間效率上得到相當(dāng)提升，例如近一兩年被熱捧的SPFA（Shortest-Path Faster Algoithm 更快的最短路徑算法）算法的時(shí)間效率甚至由于Dijkstra算法，因此成為信息學(xué)奧賽選手經(jīng)常討論的話(huà)題。然而，限于資料匱乏，有關(guān)Bellman-Ford算法的諸多問(wèn)題常常困擾奧賽選手。如：該算法值得掌握么？怎樣用編程語(yǔ)言具體實(shí)現(xiàn)？有哪些優(yōu)化？與SPFA算法有關(guān)系么？本文試圖對(duì)Bellman-Ford算法做一個(gè)比較全面的介紹。給出幾種實(shí)現(xiàn)程序，從理論和實(shí)測(cè)兩方面分析他們的時(shí)間復(fù)雜度，供大家在備戰(zhàn)省選和后續(xù)的noi時(shí)參考。
Bellman-Ford算法思想
Bellman-Ford算法能在更普遍的情況下（存在負(fù)權(quán)邊）解決單源點(diǎn)最短路徑問(wèn)題。對(duì)于給定的帶權(quán)（有向或無(wú)向）圖 G=（V,E），其源點(diǎn)為s，加權(quán)函數(shù) w是 邊集 E 的映射。對(duì)圖G運(yùn)行Bellman-Ford算法的結(jié)果是一個(gè)布爾值，表明圖中是否存在著一個(gè)從源點(diǎn)s可達(dá)的負(fù)權(quán)回路。若不存在這樣的回路，算法將給出從源點(diǎn)s到 圖G的任意頂點(diǎn)v的最短路徑d[v]。
Bellman-Ford算法流程分為三個(gè)階段：
（1） 初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值 d[v] ←+∞, d[s] ←0;
（2） 迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個(gè)頂點(diǎn)v的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次）
（3） 檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false，表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在 d[v]中。
算法描述如下：
Bellman-Ford(G,w,s) ：boolean //圖G ，邊集 函數(shù) w ，s為源點(diǎn)
1 for each vertex v ∈ V（G） do //初始化 1階段
2 d[v] ←+∞
3 d[s] ←0; //1階段結(jié)束
4 for i=1 to |v|-1 do //2階段開(kāi)始，雙重循環(huán)。
5 for each edge（u,v） ∈E(G) do //邊集數(shù)組要用到，窮舉每條邊。
6 If d[v]> d[u]+ w(u,v) then //松弛判斷
7 d[v]=d[u]+w(u,v) //松弛操作 2階段結(jié)束
8 for each edge（u,v） ∈E(G) do
9 If d[v]> d[u]+ w(u,v) then
10 Exit false
11 Exit true
下面給出描述性證明：
首先指出，圖的任意一條最短路徑既不能包含負(fù)權(quán)回路，也不會(huì)包含正權(quán)回路，因此它最多包含|v|-1條邊。
其次，從源點(diǎn)s可達(dá)的所有頂點(diǎn)如果 存在最短路徑，則這些最短路徑構(gòu)成一個(gè)以s為根的最短路徑樹(shù)。Bellman-Ford算法的迭代松弛操作，實(shí)際上就是按頂點(diǎn)距離s的層次，逐層生成這棵最短路徑樹(shù)的過(guò)程。
在對(duì)每條邊進(jìn)行1遍松弛的時(shí)候，生成了從s出發(fā)，層次至多為1的那些樹(shù)枝。也就是說(shuō)，找到了與s至多有1條邊相聯(lián)的那些頂點(diǎn)的最短路徑；對(duì)每條邊進(jìn)行第2遍松弛的時(shí)候，生成了第2層次的樹(shù)枝，就是說(shuō)找到了經(jīng)過(guò)2條邊相連的那些頂點(diǎn)的最短路徑……。因?yàn)樽疃搪窂阶疃嘀话瑋v|-1 條邊，所以，只需要循環(huán)|v|-1 次。
每實(shí)施一次松弛操作，最短路徑樹(shù)上就會(huì)有一層頂點(diǎn)達(dá)到其最短距離，此后這層頂點(diǎn)的最短距離值就會(huì)一直保持不變，不再受后續(xù)松弛操作的影響。（但是，每次還要判斷松弛，這里浪費(fèi)了大量的時(shí)間，怎么優(yōu)化？單純的優(yōu)化是否可行？）
如果沒(méi)有負(fù)權(quán)回路，由于最短路徑樹(shù)的高度最多只能是|v|-1，所以最多經(jīng)過(guò)|v|-1遍松弛操作后，所有從s可達(dá)的頂點(diǎn)必將求出最短距離。如果 d[v]仍保持 +∞，則表明從s到v不可達(dá)。
如果有負(fù)權(quán)回路，那么第 |v|-1 遍松弛操作仍然會(huì)成功，這時(shí)，負(fù)權(quán)回路上的頂點(diǎn)不會(huì)收斂。
例如對(duì)于上圖，邊上方框中的數(shù)字代表權(quán)值，頂點(diǎn)A,B,C之間存在負(fù)權(quán)回路。S是源點(diǎn)，頂點(diǎn)中數(shù)字表示運(yùn)行Bellman-Ford算法后各點(diǎn)的最短距離估計(jì)值。
此時(shí)d[a]的值為1，大于d[c]+w(c,a)的值-2，由此d[a]可以松弛為-2，然后d[b]又可以松弛為-5,d[c]又可以松弛為-7.下一個(gè)周期，d[a]又可以更新為更小的值，這個(gè)過(guò)程永遠(yuǎn)不會(huì)終止。因此，在迭代求解最短路徑階段結(jié)束后，可以通過(guò)檢驗(yàn)邊集E的每條邊(u,v)是否滿(mǎn)足關(guān)系式 d[v]> d[u]+ w(u,v) 來(lái)判斷是否存在負(fù)權(quán)回路。
二、基本 Bellman-Ford 算法的 pascal實(shí)現(xiàn)。
見(jiàn) bellmanford.pas 文件。
三、基本算法之上的優(yōu)化。
分析 Bellman-Ford算法，不難看出，外層循環(huán)（迭代次數(shù)）|v|-1實(shí)際上取得是上限。由上面對(duì)算法正確性的證明可知，需要的迭代遍數(shù)等于最短路徑樹(shù)的高度。如果不存在負(fù)權(quán)回路，平均情況下的最短路徑樹(shù)的高度應(yīng)該遠(yuǎn)遠(yuǎn)小于 |v|-1，在此情況下，多余最短路徑樹(shù)高的迭代遍數(shù)就是時(shí)間上的浪費(fèi)，由此，可以依次來(lái)實(shí)施優(yōu)化。
從細(xì)節(jié)上分析，如果在某一遍迭代中，算法描述中第7行的松弛操作未執(zhí)行，說(shuō)明該遍迭代所有的邊都沒(méi)有被松弛。可以證明（怎么證明？）：至此后，邊集中所有的邊都不需要再被松弛，從而可以提前結(jié)束迭代過(guò)程。這樣，優(yōu)化的措施就非常簡(jiǎn)單了。
設(shè)定一個(gè)布爾型標(biāo)志變量 relaxed，初值為false。在內(nèi)層循環(huán)中，僅當(dāng)有邊被成功松弛時(shí)，將 relaxed 設(shè)置為true。如果沒(méi)有邊被松弛，則提前結(jié)束外層循環(huán)。這一改進(jìn)可以極大的減少外層循環(huán)的迭代次數(shù)。優(yōu)化后的 bellman-ford函數(shù)如下。
function bellmanford(s:longint):boolean;
begin
for i:=1 to nv do
d[i]:=max;
d[s]:=0;
for i:=1 to nv-1 do
begin
relaxed:=false;
for j:=1 TO ne do
if(d[edges[j].s]<>max) and (d[edges[j].e]>d[edges[j].s]+edges[j].w)
then begin
d[edges[j].e]:=d[edges[j].s]+edges[j].w ;
relaxed:=true;
end;
if not relaxed then break;
end;
for i:=1 to ne do
if d[edges[j].e]>d[edges[j].s]+edges[j].w then exit(false);
exit(true);
end;
這樣看似平凡的優(yōu)化，會(huì)有怎樣的效果呢？有研究表明，對(duì)于隨機(jī)生成數(shù)據(jù)的平均情況，時(shí)間復(fù)雜度的估算公式為
1.13|E| if |E|<|V|
0.95*|E|*lg|V| if |E|>|V|
優(yōu)化后的算法在處理有負(fù)權(quán)回路的測(cè)試數(shù)據(jù)時(shí)，由于每次都會(huì)有邊被松弛，所以relaxed每次都會(huì)被置為true，因而不可能提前終止外層循環(huán)。這對(duì)應(yīng)了最壞情況，其時(shí)間復(fù)雜度仍舊為O(VE)。
優(yōu)化后的算法的時(shí)間復(fù)雜度已經(jīng)和用二叉堆優(yōu)化的Dijkstra算法相近了，而編碼的復(fù)雜程度遠(yuǎn)比后者低。加之Bellman-Ford算法能處理各種邊值權(quán)情況下的最短路徑問(wèn)題，因而還是非常優(yōu)秀的。Usaco3.2.6 的程序見(jiàn)bellmanford_1.pas
四、SPFA 算法
SPFA是目前相當(dāng)優(yōu)秀的求最短路徑的算法，值得我們掌握。
SPFA對(duì)Bellman-Ford算法優(yōu)化的關(guān)鍵之處在于意識(shí)到：只有那些在前一遍松弛中改變了距離估計(jì)值的點(diǎn)，才可能引起他們的鄰接點(diǎn)的距離估計(jì)值的改變。因此，用一個(gè)先進(jìn)先出的隊(duì)列來(lái)存放被成功松弛的頂點(diǎn)。初始時(shí)，源點(diǎn)s入隊(duì)。當(dāng)隊(duì)列不為空時(shí)，取出對(duì)首頂點(diǎn)，對(duì)它的鄰接點(diǎn)進(jìn)行松弛。如果某個(gè)鄰接點(diǎn)松弛成功，且該鄰接點(diǎn)不在隊(duì)列中，則將其入隊(duì)。經(jīng)過(guò)有限次的松弛操作后，隊(duì)列將為空，算法結(jié)束。SPFA算法的實(shí)現(xiàn)，需要用到一個(gè)先進(jìn)先出的隊(duì)列 queue 和一個(gè)指示頂點(diǎn)是否在隊(duì)列中的 標(biāo)記數(shù)組 mark。為了方便查找某個(gè)頂點(diǎn)的鄰接點(diǎn)，圖采用臨界表存儲(chǔ)。
程序存儲(chǔ)在 spfa.pas中。以usaco 3.2.6 試題2為例。用鄰接表寫(xiě)的程序。
需要注意的是：僅當(dāng)圖不存在負(fù)權(quán)回路時(shí)，SPFA能正常工作。如果圖存在負(fù)權(quán)回路，由于負(fù)權(quán)回路上的頂點(diǎn)無(wú)法收斂，總有頂點(diǎn)在入隊(duì)和出隊(duì)往返，隊(duì)列無(wú)法為空，這種情況下SPFA無(wú)法正常結(jié)束。
判斷負(fù)權(quán)回路的方案很多，世間流傳最廣的是記錄每個(gè)結(jié)點(diǎn)進(jìn)隊(duì)次數(shù)，超過(guò)|V|次表示有負(fù)權(quán)
還有一種方法為記錄這個(gè)結(jié)點(diǎn)在路徑中處于的位置，ord[i]，每次更新的時(shí)候ord[i]=ord[x]+1，若超過(guò)|V|則表示有負(fù)圈.....
其他方法還有很多，我反倒覺(jué)得流傳最廣的方法是最慢的.......
關(guān)于SPFA的時(shí)間復(fù)雜度，不好準(zhǔn)確估計(jì)，一般認(rèn)為是 O（kE），k是常數(shù)
五、時(shí)間效率實(shí)測(cè)
上述介紹的Bellman-Ford算法及兩種的優(yōu)化，只是在理論上分析了時(shí)間復(fù)雜度，用實(shí)際的數(shù)據(jù)測(cè)試，會(huì)有什么結(jié)果呢？為此，我們選擇 usaco 3.2.6。
Spfa的時(shí)間效率還是很高的。并且spfa的編程復(fù)雜度要比Dijksta+heap優(yōu)化要好的多。
六、結(jié)論
經(jīng)過(guò)優(yōu)化Bellman-Ford算法是非常優(yōu)化的求單源最短路徑的算法，SPFA時(shí)間效率要優(yōu)于第一種優(yōu)化形式，但第一種優(yōu)化形式的編碼復(fù)雜度低于SPFA。兩種優(yōu)化形式的編程復(fù)雜度都低于Dijkstra算法。如果在判斷是否存在負(fù)權(quán)回路，推薦使用第一種優(yōu)化形式，否則推薦使用SPFA。