Dijkstra的算法和周期 [英] Dijkstra's Algorithm and Cycles

问题描述

在一本书中提到 Dijkstra的算法仅适用于有向无环图。

It's stated in a book that "Dijkstra's algorithm only works with Directed Acyclic Graphs".

看来，只要没有负周期，该算法也适用于有周期的图。

It appears the algorithm works for graphs with cycles too as long as there are no negative cycles. Is that correct?

编辑1：
这本书 Grokking Algorithms-Aditya Bhargava。
第7章。第122页。

Edit 1: The book "Grokking Algorithms" -Aditya Bhargava. Chapter 7. Page 122.

推荐答案

我是 Grokking Algorithms 的作者。抱歉，此错误-只要是正权重周期，Dijkstra的算法确实即可在具有周期的图形上运行。我已经更新了勘误页面以反映此错误。 Dijkstra不适用于负重量周期，这是一张图片，解释原因：

I'm the author of Grokking Algorithms. Sorry for this error—Dijkstra's algorithm does work on graphs with cycles, as long as it is a positive weight cycle. I have updated the errata page to reflect this error. Dijkstra's doesn't work on negative weight cycles, and here's an image that explains why:

这篇关于Dijkstra的算法和周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！