貝爾曼-福特算法

鎖定

貝爾曼-福特算法（英語：Bellman–Ford algorithm），求解單源最短路徑問題的一種算法，由理查德·貝爾曼（Richard Bellman） 和萊斯特·福特創立的。有時候這種算法也被稱為 Moore-Bellman-Ford 算法，因為Edward F. Moore也為這個算法的發展做出了貢獻。它的原理是對圖進行

次鬆弛操作，得到所有可能的最短路徑。其優於迪科斯徹算法的方面是邊的權值可以為負數、實現簡單，缺點是時間複雜度過高，高達

。但算法可以進行若干種優化，提高了效率。

貝爾曼-福特算法與迪科斯徹算法類似，都以鬆弛操作為基礎，即估計的最短路徑值漸漸地被更加準確的值替代，直至得到最優解。在兩個算法中，計算時每個邊之間的估計距離值都比真實值大，並且被新找到路徑的最小長度替代。 然而，迪科斯徹算法以貪心法選取未被處理的具有最小權值的節點，然後對其的出邊進行鬆弛操作；而貝爾曼-福特算法簡單地對所有邊進行鬆弛操作，共

次，其中

是圖的點的數量。在重複地計算中，已計算得到正確的距離的邊的數量不斷增加，直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特算法比迪科斯徹算法適用於更多種類的輸入。

貝爾曼-福特算法的最多運行

（大O符號）次，

和

分別是節點和邊的數量）。

procedure BellmanFord(list vertices, list edges, vertex source)
   // 該實現讀入邊和節點的列表，並向兩個數組（distance和predecessor）中寫入最短路徑信息

   // 步驟1：初始化圖
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // 步驟2：重複對每一條邊進行鬆弛操作
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // 步驟3：檢查負權環
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "圖包含了負權環"

每次鬆弛操作實際上是對相鄰節點的訪問，第

次鬆弛操作保證了所有深度為n的路徑最短。由於圖的最短路徑最長不會經過超過

條邊，所以可知貝爾曼-福特算法所得為最短路徑。

因為負權環可以無限制的降低總花費，所以如果發現第

次操作仍可降低花銷，就一定存在負權環。 ^[1] 

在實際操作中，貝爾曼-福特算法經常會在未達到

次前就出解，

其實是最大值。於是可以在循環中設置判定，在某次循環不再進行鬆弛時，直接退出循環，進行負權環判定。

西南交通大學的段凡丁於1994年提出了用隊列來優化的算法。鬆弛操作必定只會發生在最短路徑前導節點鬆弛成功過的節點上，用一個隊列記錄鬆弛過的節點，可以避免了冗餘計算。原文中提出該算法的複雜度為

，

是個比較小的係數，但該結論未得到廣泛認可。 ^[2] 

Begin
 2   initialize-single-source(G,s);
 3   initialize-queue(Q);
 4   enqueue(Q,s);
 5   while not empty(Q) do 
 6     begin
 7       u:=dequeue(Q);
 8       for each v∈adj[u] do 
 9         begin
10           tmp:=d[v];
11           relax(u,v);
12           if (tmp<>d[v]) and (not v in Q) then
13             enqueue(Q,v);
14         end;
15     end;
16 End;

int SPFA(int s) {
 2     queue<int> q;
 3     bool inq[maxn] = {false};
 4     for(int i = 1; i <= N; i++) dis[i] = 2147483647;
 5     dis[s] = 0;
 6     q.push(s); inq[s] = true;
 7     while(!q.empty()) {
 8         int x = q.front(); q.pop();
 9         inq[x] = false;
10         for(int i = front[x]; i !=0 ; i = e[i].next) {
11             int k = e[i].v;
12             if(dis[k] > dis[x] + e[i].w) {
13                 dis[k] = dis[x] + e[i].w;
14                 if(!inq[k]) {
15                     inq[k] = true;
16                     q.push(k);
17                 }
18             }
19         }
20     }
21     for(int i =  1; i <= N; i++) cout << dis[i] << ' ';
22     cout << endl;
23     return 0;
24 }

參考資料

• 1.    Bang-Jensen, Jørgen; Gutin, Gregory (2000). "Section 2.3.4: The Bellman-Ford-Moore algorithm". Digraphs: Theory, Algorithms and Applications (First ed.). ISBN 978-1-84800-997-4.
• 2.    Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). "Chapter 6: Graph Algorithms". Algorithms in a Nutshell. O'Reilly Media. pp. 160–164. ISBN 978-0-596-51624-6.