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

回答