Dijkstra的算法和循環

它在書中說「Dijkstra算法只適用於有向非循環圖」。Dijkstra的算法和循環

看來，只要沒有負循環，該算法也適用於循環圖。那是對的嗎？

編輯1：書「Grokking Algorithms」-Aditya Bhargava。第7章第122頁。

2017-04-13 sam

如果你指的是「最短路徑算法」，當然它工作循環圖...您的報價是錯誤的。 –

如果我可以問哪本書？如果你能提供更多的細節在哪裏可以找到這樣的報價，那將是非常好的。 – maxik

實際上，只要所有邊權重都是非負數，它就會起作用。這是一個更強有力的條件，因爲「無負面循環」。另一方面，它不適用於負面權重的DAG。所以，只要你引用正確，這本書的陳述是錯誤的，原因有兩個。

順便說一句。如果你有負循環，那麼可能不再是最短路徑，因爲你可以循環無數次，並隨着你的成本降低成本。

2017-04-13 14:32:05 Henry

謝謝@亨利 – sam

我是的作者Grokking Algorithms。對不起，這個錯誤-Dijkstra的算法確實在循環圖上工作，只要它是一個正的權重循環。我已更新errata page以反映此錯誤。 Dijkstra的不負重量循環工作，這裏的解釋了爲什麼圖像：

dijkstra's algorithm with a negative weight cycle

2017-05-06 16:39:24

回答