Bellman-Ford 算法(帶權有向圖最短路徑算法)

Bellman-Ford算法（根據發明者 Richard Bellman 和 Lester Ford 命名）是求解單源最短路徑問題的一種算法。有時候這種算法也被稱為 Moore-Bellman-Ford 算法，因為 Edward F. Moore 也為這個算法的發展做出了貢獻。
單源點的最短路徑問題是指：給定一個加權有向圖G和源點s，對於圖G中的任意一點v，求從s到v的最短路徑。
與迪傑斯特拉算法，（另一種著名的求最短路徑的算法）不同的是，在 Bellman-Ford 算法中，路徑的權值可以為負數。 設想從我們可以從圖中找到一個環路（即從v出發，經過若干個點之後又回到v）且這個環路中所有路徑的權值之和為負。那麼通過這個環路，環路中任意兩點的最 短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。 而Bellman-Ford算法具有分辨這種負環路的能力。

算法描述

設G為加權有向圖 V是所有結點的集合 E是所有路徑的集合 S表示源點 n表示V中所有結點的數目 weight(u,v)表示從結點u到結點v的路徑的權值。 Distanz(v)表示從源點s出發到結點v的最短路徑的距離，（或者說是從s到v所有的路徑中權值的最小值）。【Predecessor(v)表示節 點v的父結點。】在Bellman-Ford算法結束之後，可以輸出，G是不是包含一個負環路。如果G不包含負環路，那麼Distanz就存儲了從s出發 到所有結點的距離。

Bellman-Ford 算法是 SPFA 算法的基礎算法。SPFA 算法是 Bellman-Ford 算法的加強版，時間複雜度和適用面都優於 Dijkstra 算法。設G = (V,E,W) 為某一有向帶權圖（W 即 weight，權值），s，t 分別代表源點和終點，Distance(v) 代表 v 在算法當前階段中暫定的從源點出發的最短權和，則算法的核心思想是進行至多 |V|-1 次的迭代處理，每次從 s 出發擴展一層路徑，逐漸逼近最短路徑。

Bellman-Ford算法的偽代碼如下：

for 每一個結點v ∈ V
   Distance(v) := +∞
Distance(s) := 0
 循環 n-1 次
     for 每一條路徑 （u,v）∈ E
         if Distance(u) + weight(u,v) < Distance(v) then
            Distance(v) := Distance(u) + weight(u,v)
 for 每一條路徑 （u，v）屬於 E
     if Distance(u) + weight(u,v) < Distance(v)
     then 中止程序並且返回 「找到負循環」
 返回 執行成功

for 每一個結點v ∈ V
Distance(v) := +∞
Distance(s) := 0
循環 n-1 次
for 每一條路徑 （u,v）∈ E
if Distance(u) + weight(u,v) < Distance(v) then
Distance(v) := Distance(u) + weight(u,v)
for 每一條路徑 （u，v）屬於 E
if Distance(u) + weight(u,v) < Distance(v)
then 中止程序並且返回 「找到負循環」
返回 執行成功

第一次迭代時，Distance(s)=0，而對於任意 v ∈ V 且 v <> s，Distance(v)=+∞。因此第一次執行時，從偽代碼可以看出，該算法實質是找到了從點 s 出發的所有邊並更新了這些邊的其非源端點到源點的Distance距離為這些邊本身的權值。

第二次迭代時，對於所有 Distance(v) 不為無窮大的非源點，其 Distance 值即是從 s 出發的某條邊的權值。在這次迭代中，在進行

 if Distance(u) + weight(u,v) < Distance(v)
         then
            Distance(v) := Distance(u) + weight(u,v) 

if Distance(u) + weight(u,v) < Distance(v)
then
Distance(v) := Distance(u) + weight(u,v)

即 更新 Distance 的值的過程中，新得到的 Distance(v) 由兩部分組成，一部分是 Distance(u)，上文已說明它們中存儲的是從點 s 出發的各個邊的權值，一部分是 weight(u,v)，也即 Distance(v) 中最終存儲的是從 s 出發的經過兩層（兩條邊）到達 v 的路徑長度。

以此類推，每次執行迭代後，均為按層擴展（或稱增廣），每次都可能更新 Distance(v)，其實質是通過更多層數換取更小的權值，經過了最多 |V|-1 次的增廣，即可保證得到了從 s 出發到任意一個點的最短路徑，並存儲在了 Distance(v) 中。

如有任何疑問或對本文所述內容有任何不解或本文發現錯誤，敬請提出或批評指正。