Can you summarize the following document?
        
  貝爾曼-福特演算法與迪科斯徹演算法類似,都以鬆弛操作為基礎,即估計的最短路徑值漸漸地被更加準確的值替代,直至得到最優解。在兩個演算法中,計算時每個邊之間的估計距離值都比真實值大,並且被新找到路徑的最小長度替代。 然而,迪科斯徹演算法以貪心法選取未被處理的具有最小權值的節點,然後對其的出邊進行鬆弛操作;而貝爾曼-福特演算法簡單地對所有邊進行鬆弛操作,共formula_3次,其中formula_4是圖的點的數量。在重複地計算中,已計算得到正確的距離的邊的數量不斷增加,直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特演算法比迪科斯徹演算法適用於更多種類的輸入。  貝爾曼-福特演算法的最多執行formula_5(大O符號)次,formula_6和formula_7分別是節點和邊的數量)。

  procedure BellmanFord("list" vertices, "list" edges, "vertex" source)

  

  每次迴圈操作實際上是對相鄰節點的訪問,第formula_8次迴圈操作保證了所有深度為n的路徑最短。由於圖的最短路徑最長不會經過超過formula_3條邊,所以可知貝爾曼-福特演算法所得為最短路徑。

  與迪科斯徹演算法不同的是,迪科斯徹演算法的基本操作“拓展”是在深度上尋路,而“鬆弛”操作則是在廣度上尋路,這就確定了貝爾曼-福特演算法可以對負邊進行操作而不會影響結果。

  因為負權環可以無限制的降低總花費,所以如果發現第formula_8次操作仍可降低花銷,就一定存在負權環。

  當使用這個演算法尋找最短路徑時,有負迴路會使演算法找不到正確的答案。但是,由於在找到負迴路後會中止演算法,所以可以被用來尋找目標,例如在網路流分析中的消圈演算法(Cycle Cancellation Algorithms)

  

  在實際操作中,貝爾曼-福特演算法經常會在未達到formula_11次前就出解,formula_11其實是最大值。於是可以在迴圈中設定判定,在某次迴圈不再進行鬆弛時,直接退出迴圈,進行負權環判定。

  西南交通大學的段凡丁於1994年提出了用佇列來優化的演算法。鬆弛操作必定只會發生在最短路徑前導節點鬆弛成功過的節點上,用一個佇列記錄鬆弛過的節點,可以避免了冗餘計算。原文中提出該演算法的複雜度為formula_13,formula_14是個比較小的係數,但該結論被證明不適于于所有情況。  Pascal語言示例  C++語言示例 int SPFA(int s) {

  例:  執行如表: formula_16
貝爾曼-福特演算法(英語:Bellman–Ford algorithm),求解單源最短路徑問題的一種演算法,由理查德·貝爾曼(Richard Bellman) 和 萊斯特·福特 創立的。有時候這種演算法也被稱為 Moore-Bellman-Ford 演算法,因為 Edward F. Moore 也為這個演算法的發展做出了貢獻。它的原理是對圖進行formula_1次鬆弛操作,得到所有可能的最短路徑。其優於迪科斯徹演算法的方面是邊的權值可以為負數、實現簡單,缺點是時間複雜度過高,高達formula_2。但演算法可以進行若干種優化,提高了效率。