Dijkstra的算法和周期

Question

在一本书中指出"Dijkstra算法仅适用于有向无环图".

只要没有负循环,该算法似乎适用于具有周期的图形.那是对的吗？

编辑1:书"Grokking Algorithms"-Aditya Bhargava.第7章.第122页.

Answer 1

我是Grokking Algorithms的作者.对于这个错误很抱歉 - Dijkstra的算法确实适用于具有周期的图形,只要它是一个正的权重周期.我更新了勘误页面以反映此错误.Dijkstra's不适用于负重量周期,这是一个解释原因的图像:

Answer 2

实际上，只要所有边的权重都是非负的，它就可以工作。这是“无负循环”的更强条件。另一方面，它不适用于负权重的 DAG。所以，如果你引用正确，书中的陈述是错误的，原因有两个。

顺便提一句。如果您有负循环，则可能不再有最短路径，因为您可能会循环无限次并随心所欲地降低成本。