为什么我们不能将 Dijkstra 算法应用于具有负权重的图？
最佳答案
如果每次从 C 到 D 旅行都得到报酬，那么找到从 A 到 B 的最便宜的路径意味着什么？
如果两个节点之间存在负权重，则“最短路径”将永远在这两个节点之间向后和向前循环。跳数越多，路径就越“短”。
这与算法无关，与无法回答这样的问题有关。
编辑 :
上述声明假定双向链接。如果没有整体负权重的周期，你就没有办法永远循环，获得报酬。
在这种情况下，Dijkstra 算法可能仍然失败:
考虑两条路径:
Dijkstra 算法将首先调查次优路径，并在找到时宣布自己已完成。它永远不会跟进比找到的第一个解决方案更糟糕的子路径
关于dijkstra - 为什么我们不能将 Dijkstra 算法应用于具有负权重的图？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3200446/