貝爾曼-福特演算法

貝爾曼-福特演算法（英語：Bellman–Ford algorithm）， 求解單源上短路徑問題的一種演算法，由理察 ・ 貝爾曼和小萊斯特 ・ 倫道夫 ・ 福特創立。有當時仔這種演算法嘛予人號做 Moore-Bellman-Ford 演算法，因為愛德華 ・ F ・ 摩爾嘛為這个演算法的發展做出了貢獻。伊的原理是對圖咧進行 $ | V | 影一 $ 次鹿楝操作，得著所有可能的上短路徑。其優於迪科斯徹演的算法的方面是邊的權值會當為負數、實現簡單，缺點是時間複雜度傷懸，懸到位 $ O ( | V | | E | ) $。但是演算法會當進行若干種最佳化，提懸著效率。

演算法

貝爾曼-福特演算法佮迪科斯徹演算法類似，攏用鹿楝操作為基礎，即估計的上短路徑值漸漸予人閣較準確的值替代，一直到得著最佳解。佇咧兩个演算法內底，算時𪜶每一个邊之間的估計距離值攏比真實值大，並且予新揣著路徑的上小長度替代。 毋過，迪科斯徹演算法以貪婪法選取未予人處理的具有上小權值的節點，然後對其的出現進行鹿楝操作；而貝爾曼-福特演算法簡單的對所有的那進行鹿楝操作，共 $ | V | 影一 $ 次，其中 $ | V | $ 是圖的點的數量。佇重複地計算中，已經算得著正確的距離的邊仔的數量不斷增加，到甲所有那攏計算得著矣正確的路徑。這款的策略予得貝爾曼-福特演算法比迪科斯徹演算法適用佇閣較濟種的輸入。

貝爾曼-福特演算法的上濟執行 $ O ( | V | \ cdot | E | ) $（大 O 符號）次，$ | V | $ 和 $ | E | $ 分別是節點佮邊的數量）。

虛擬碼

` ` ` procedureBellmanFord ( _ list _ vertices , _ list _ edges , _ vertex _ source ) / / 讀入邊佮節點的列表並著 distance 和 predecessor 寫入上短路徑

/ / 初初去化圖 for eachvertex vinvertices : ifvissourcethendistance [v]   :=零 elsedistance [v]   :=infinity predecessor [v]   :=null

/ / 嘿每一條邊重複操作 forifrom一tosize ( vertices ) 影一 : for eachedge ( u , v )withweight winedges : ifdistance [u] + w < distance [v] : distance [v]   :=distance [u] + w predecessor [v]   :=u

/ / 檢查敢有負權重的回路 for eachedge ( u , v )withweight winedges : ifdistance [u] + w < distance [v] : error" 圖包含負權重的回路 " ` ` `

原理

迴箍

逐改迴圈操作實際上是對相鄰節點的存取，第 $ n $ 改迴圈操作有保證所有的深度為 n 的路草上短。因為圖的上短路徑上長袂經過超過 $ | V | 影一 $ 條邊，所以會當知貝爾曼-福特演算法所得為上短路徑。

負邊權操作

佮迪科斯徹演的算法無仝的是，迪科斯徹演算法的基本操作「拓展」是佇咧深度上揣路，而且「鹿楝」操作則是佇咧廣度揣路，這就確定了貝爾曼-福特演算法會當對負邊進行操作啊若袂影響結果。

負權環判定

因為負權環會使無限制的降低總開開，所以若發現第一个 $ n $ 操作猶是會當降低花銷，就一定存在負權環。

走揣負迴路

當使用這个演算法走揣上短路徑的時陣，有負迴路會當演算法揣無正確的答案。猶毋過，因為佇咧揣著負迴路後會中止演算法，所以會當予人來走揣目標，比如講佇網路頂懸分析中的消箍演算法 ( Cycle Cancellation Algorithms )

最佳化

迴箍仔的進前跳出

佇實際操作中，貝爾曼-福特演算法定定會佇咧無達到 $ | V | 影一 $ 過去就出解講，$ | V | 影一 $ 其實是上大的值。所以會當佇迴箍內底設定判定，佇咧某一擺迴圈無閣進行鹿楝的時陣，直接登出迴圈，進行負權環判定。

在列最佳化

西南交通大學的段凡丁佇一九九四年提出矣用佇列來最佳化的演算法。鹿楝操作必定只會發生佇咧上短路徑前導節點鹿楝成功過的節點上，用一个佇咧列記錄鹿楝過的節點，會當避免趁錢的計算。原文內底提出該演算法的複雜度做 $ O ( k | E | ) $，$ k $ 是一个較細項的係數，但是結論被證明無爽快于所有的情形。

Pascal 語言範例

C + + 語言範例

看仿

例：

$ V=\ { v _ { 一 } , v _ { 二 } , v _ { 三 } , v _ { 四 } \ } , E=\ { ( v _ { 一 } , v _ { 二 } ) , ( v _ { 一 } , v _ { 三 } ) , ( v _ { 二 } , v _ { 四 } ) , ( v _ { 四 } , v _ { 三 } ) \ } $，$ weight ( v _ { 一 } , v _ { 二 } )=影一 , weight ( v _ { 一 } , v _ { 三 } )=三 , weight ( v _ { 二 } , v _ { 四 } )=三 , weight ( v _ { 四 } , v _ { 三 } )=影一 $。

執行如表：$ D : { \ texttt { Dist } } [v] , P : { \ texttt { Pred } } [v] $