infinity

Bellman-Ford 算法及其優(yōu)化

Bellman-Ford算法與另一個非常著名的Dijkstra算法一樣，用于求解單源點最短路徑問題。Bellman-ford算法除了可求解邊權(quán)均非負的問題外，還可以解決存在負權(quán)邊的問題（意義是什么，好好思考），而Dijkstra算法只能處理邊權(quán)非負的問題，因此 Bellman-Ford算法的適用面要廣泛一些。但是，原始的Bellman-Ford算法時間復雜度為 O（VE）,比Dijkstra算法的時間復雜度高，所以常常被眾多的大學算法教科書所忽略，就連經(jīng)典的《算法導論》也只介紹了基本的Bellman-Ford算法，在國內(nèi)常見的基本信息學奧賽教材中也均未提及，因此該算法的知名度與被掌握度都不如Dijkstra算法。事實上，有多種形式的Bellman-Ford算法的優(yōu)化實現(xiàn)。這些優(yōu)化實現(xiàn)在時間效率上得到相當提升，例如近一兩年被熱捧的SPFA（Shortest-Path Faster Algoithm 更快的最短路徑算法）算法的時間效率甚至由于Dijkstra算法，因此成為信息學奧賽選手經(jīng)常討論的話題。然而，限于資料匱乏，有關(guān)Bellman-Ford算法的諸多問題常常困擾奧賽選手。如：該算法值得掌握么？怎樣用編程語言具體實現(xiàn)？有哪些優(yōu)化？與SPFA算法有關(guān)系么？本文試圖對Bellman-Ford算法做一個比較全面的介紹。給出幾種實現(xiàn)程序，從理論和實測兩方面分析他們的時間復雜度，供大家在備戰(zhàn)省選和后續(xù)的noi時參考。

Bellman-Ford算法思想

Bellman-Ford算法能在更普遍的情況下（存在負權(quán)邊）解決單源點最短路徑問題。對于給定的帶權(quán)（有向或無向）圖 G=（V,E），其源點為s，加權(quán)函數(shù) w是 邊集 E 的映射。對圖G運行Bellman-Ford算法的結(jié)果是一個布爾值，表明圖中是否存在著一個從源點s可達的負權(quán)回路。若不存在這樣的回路，算法將給出從源點s到 圖G的任意頂點v的最短路徑d[v]。

Bellman-Ford算法流程分為三個階段：

（1）    初始化：將除源點外的所有頂點的最短距離估計值 d[v] ←+∞, d[s] ←0;

（2）    迭代求解：反復對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離；（運行|v|-1次）

（3）    檢驗負權(quán)回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回false，表明問題無解；否則算法返回true，并且從源點可達的頂點v的最短距離保存在 d[v]中。

算法描述如下：

Bellman-Ford(G,w,s) ：boolean   //圖G ，邊集 函數(shù) w ，s為源點

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階段開始，雙重循環(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

下面給出描述性證明：

   首先指出，圖的任意一條最短路徑既不能包含負權(quán)回路，也不會包含正權(quán)回路，因此它最多包含|v|-1條邊。

   其次，從源點s可達的所有頂點如果 存在最短路徑，則這些最短路徑構(gòu)成一個以s為根的最短路徑樹。Bellman-Ford算法的迭代松弛操作，實際上就是按頂點距離s的層次，逐層生成這棵最短路徑樹的過程。

在對每條邊進行1遍松弛的時候，生成了從s出發(fā)，層次至多為1的那些樹枝。也就是說，找到了與s至多有1條邊相聯(lián)的那些頂點的最短路徑；對每條邊進行第2遍松弛的時候，生成了第2層次的樹枝，就是說找到了經(jīng)過2條邊相連的那些頂點的最短路徑……。因為最短路徑最多只包含|v|-1 條邊，所以，只需要循環(huán)|v|-1 次。

每實施一次松弛操作，最短路徑樹上就會有一層頂點達到其最短距離，此后這層頂點的最短距離值就會一直保持不變，不再受后續(xù)松弛操作的影響。（但是，每次還要判斷松弛，這里浪費了大量的時間，怎么優(yōu)化？單純的優(yōu)化是否可行？）

如果沒有負權(quán)回路，由于最短路徑樹的高度最多只能是|v|-1，所以最多經(jīng)過|v|-1遍松弛操作后，所有從s可達的頂點必將求出最短距離。如果 d[v]仍保持 +∞，則表明從s到v不可達。

如果有負權(quán)回路，那么第 |v|-1 遍松弛操作仍然會成功，這時，負權(quán)回路上的頂點不會收斂。

例如對于上圖，邊上方框中的數(shù)字代表權(quán)值，頂點A,B,C之間存在負權(quán)回路。S是源點，頂點中數(shù)字表示運行Bellman-Ford算法后各點的最短距離估計值。

此時d[a]的值為1，大于d[c]+w(c,a)的值-2，由此d[a]可以松弛為-2，然后d[b]又可以松弛為-5,d[c]又可以松弛為-7.下一個周期，d[a]又可以更新為更小的值，這個過程永遠不會終止。因此，在迭代求解最短路徑階段結(jié)束后，可以通過檢驗邊集E的每條邊(u,v)是否滿足關(guān)系式 d[v]> d[u]+ w(u,v) 來判斷是否存在負權(quán)回路。