使用Bellman-Ford算法：什麼是遍歷每條邊的正確方法？

Question

我正在做一個家庭作業問題，我需要從頂點z開始運行bellman-ford算法。它希望我「在每次傳球時，按照與圖中相同的順序放鬆邊緣，並在每次傳球后顯示d和pi值。」 從我所瞭解的情況來看，我認爲這個算法像BFS一樣遍歷圖形，從他們希望我使用的圖形中有意義，所以我不知道同一條路徑如何工作。如果任何人都可以通過指出如何啓動它來指出正確的方向，那將是非常有用的。現在的問題，問題是參照本圖：

Answer 1

我會嘗試指出你的錯誤。

我想這個算法中穿過像BFS

這是不正確的圖形。這個算法重複遍歷圖的所有邊，並「放鬆」它們直到它達到穩定狀態（當沒有放鬆可以再做時）

你附加的例子有點混亂，類似於BFS執行。這是因爲在每次迭代中，它們只會加粗影響節點值的邊緣（放鬆的邊緣）。

所以，要回答你的問題，選擇任何順序的邊緣，並開始所謂的「放鬆」他們。對於每條邊，將它的指向節點d的值設置爲離Z最遠的最短距離，並將其設置爲它的前驅節點。重複此操作直至所有值穩定。

希望能回答你的問題。

Answer 2

正如Ido.Co所說，在Bellman Ford中沒有特定的掃描/迭代順序。但據說掃描寬度的第一種方式，執行速度更快。