Floyd Warshall算法在負重循環中的時間複雜度

Question

我知道在圖中存在負的權重循環時沒有找到最小距離的方法，那麼就沒有最小距離的含義。我的問題是，如果我們將Floyd Warshall算法與負重量週期的圖形一起填充會發生什麼？它會無限期運行或終止（可能是錯誤的答案）在O（n ）？

Answer 1

正如你可能找到的Wikipedia
Floyd-Warshall算法沒有條件是基於當前的權重或最大權重。
算法只是通過所有的頂點對並計算距離。 所以答案是否定的，它不會無限期地運行。
絕對算法會返回錯誤的答案（對於消極循環中的頂點，您將有負距離）。例如，從頂點到它自身的距離是負的。

此外，該算法也可用於負循環檢測。