Dijkstra算法和循环

Question

一本书中提到：“Dijkstra算法仅适用于有向无环图(Directed Acyclic Graphs)。”

实际上，只要没有负权重的环路，该算法也可以用于带有环路的图。这个说法正确吗？

编辑1：书名《算法图解》 (Grokking Algorithms) - Aditya Bhargava, 第7章，第122页。

- sam

---

如果你在提到“最短路径算法”，那么它当然适用于循环图... 你引用的是错误的。 - Jean-Baptiste Yunès

请问是哪本书？如果您能提供更多细节以便找到这个引用，那就太好了。 - maxik

Answer 1

我是《算法图解》的作者。对于这个错误表示歉意——Dijkstra算法可以处理具有正权重环的图形。 我已更新勘误页面以反映此错误。 Dijkstra算法无法处理具有负权重环的情况，以下是说明其原因的图片：

- Aditya Bhargava

---

我也在读你的书。但是我发现，如果我保留一个处理过的数组来跟踪已计算的节点，它也适用于负权重循环。如果它不返回已标记为已处理的节点，则不会陷入循环中。我感到困惑。我在这里进行了一些实验（链接：https://s3-ap-southeast-1.amazonaws.com/image-for-articles/image-bucket-1/negative-cycle.jpg）。 - Xullnn

正如@Henry在另一条评论中提到的那样，Dijkstra算法无法处理带有负权边的图，即使该图是无环的：https://dev59.com/pojca4cB1Zd3GeqPz6cO#28997340 - zzzzzzz

Answer 2

实际上，只要所有边权值都是非负数，它就可以工作。这是比“没有负环”更强的条件。另一方面，它不能在具有负权重的DAG上工作。因此，如果你引用的正确，那么从书中得出的结论是错误的，原因有两个。

顺便说一下，如果有负环，可能不再存在最短路径，因为你可以无限循环并以任意成本下降。

- Henry

Answer 3

如果有人正在寻找一个具有负权值的示例DAG，而Dijkstra算法不能给出正确的最短路径，请参考以下链接：https://dev59.com/q2w15IYBdhLWcg3wJ4YR#6799344

- Nikhil