爲什麼Bellman Ford算法的第一次迭代中沒有放寬所有邊？

Bellman ford算法請參考以下頁面（顯示例如）。 http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm 爲什麼Bellman Ford算法的第一次迭代中沒有放寬所有邊？

我還是不明白。在外循環的第一次循環迭代中，假設通過這個例子，首先修改邊1-> 2和邊1-> 4，放寬邊2-> 3，2-> 5，4- > 3,4-> 5，在同一步驟中，因爲我們有d [2]和d [4]。

set toRelax = {initial_vertex} 
while toRelax is not empty: 
    u = remove a vertex from toRelax 
    for each neighbour v of u: 
     if we can relax u-v: 
      relax u-v 
      add v to toRelax

通知了每個「臺階」現在涉及到一個頂點：如果使用sligtly不同版本的貝爾曼 - 福特的

來源

2011-11-21 shahalpk

沒有問題。你可以做到這一點，事實上你鏈接的代碼可以做到這一點（或者可以，取決於邊緣在輸入文件中出現的順序）。您剛剛選擇了特定訂單來放鬆邊緣，從而獲得滿意的結果。在鏈接文章中，每次通過鬆弛步驟檢查所有邊，並且在每個邊放寬時更新距離，因此可以想象特定圖在所有第一次鬆弛迭代結束時所有邊都將完全放鬆。 –

這個問題奇蹟般地消失了！在「同一步驟」中完成的事情只是您使用的特定實現的人爲因素，最終並未真正改變算法。

來源

2011-11-21 16:44:16 hugomg

我非常喜歡這個版本。你只是試圖放鬆有機會改變當前狀態的邊緣。文獻中有關於這種方法的內容嗎？它真的還是B-F嗎？這似乎是一個迭代的Dijkstra's，它不是一步優化一個頂點，而是在步驟中獲得儘可能好的結果，同時保留將來重新訪問它的權利。 –

但似乎這種方法失去了檢測負循環的能力。 http://stackoverflow.com/questions/29817131/bellman-ford-queue-based-approach-from-sedgewick-and-wayne-algorithms-4th-edi?rq=1 –

爲什麼Bellman Ford算法的第一次迭代中沒有放寬所有邊？

回答

相關問題