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