一本书上说“Dijkstra 算法只适用于有向无环图”。
只要没有负环，该算法似乎也适用于有环的图。对吗？
编辑 1: 《Grokking 算法》一书 - Aditya Bhargava。 第 7 章第 122 页。
最佳答案
我是 Grokking Algorithms 的作者。对于这个错误，我们深表歉意——Dijkstra 的算法确实适用于具有循环的图，只要它是一个正权重循环。我已经更新了 errata page来反射(reflect)这个错误。 Dijkstra 不适用于负权重循环，这里有一张图片解释了原因:
关于algorithm - Dijkstra 算法和循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43394847/