我目前正在研究 Bellman-Ford 演算法，突然出現了一個疑問。據我所知，Bellman-Ford 演算法從其源中創建最短路徑，如果圖中可能存在負回圈，它回傳 true 并且演算法停止，另一方面，它回傳 false 并回傳最短路徑。
我現在的問題是，該演算法是否避免了圖中的正回圈以創建最短路徑，還是只是不考慮它們（因此落入陷阱）？
提前致謝！
uj5u.com熱心網友回復：
如果存在負回圈，則沒有“最短”路徑，因為您可以隨心所欲地圍繞回圈進行多次，以使路徑“更短”（即邊緣權重的總和更低）。如果圖有負回圈，那么演算法可能會因陷入無限回圈或回傳不是最短的路徑而失敗；因此，我們對能夠“檢測”負回圈并且不會以其中一種方式失敗的演算法感興趣。
Bellman-Ford 就是這種演算法的一個例子：如果圖有一個負回圈，那么 Bellman-Ford 演算法檢測到沒有最短路徑（并且可以報告負回圈是什么）。這意味著該演算法正確地確定了尋找最短路徑的問題對該輸入沒有定義的解決方案，而不是給出錯誤的結果或未能終止。
正回圈不會產生任何類似的問題，因為正回圈的存在并不意味著沒有最短路徑。任意多次繞正回圈的解決方案會導致更長的路徑（即更高的邊權重總和），而不是更短的路徑。所以每個最短路徑演算法都必須正確處理這種情況，包括 Bellman-Ford。
uj5u.com熱心網友回復：
考慮一個包含正權重的回圈 <a,b,c,a>。很明顯，如果我們將源到頂點a的最短距離設定為邊c到a，那么這將與最短路徑的最優子結構和Belman-Ford演算法的正確性相矛盾。因此該演算法評估正回圈的長度，但不將其視為最短路徑。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409371.html
標籤：
上一篇：簡單平衡問題的簡單演算法