Dijkstra的算法和周期

本文介绍了Dijkstra的算法和周期的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在一本书中提到 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: