dijkstra - 为什么我们不能将 Dijkstra 算法应用于具有负权重的图？

Question

为什么我们不能将 Dijkstra 算法应用于具有负权重的图？

Answer 1

如果每次从 C 到 D 旅行都得到报酬，那么找到从 A 到 B 的最便宜的路径意味着什么？

如果两个节点之间存在负权重，则“最短路径”将永远在这两个节点之间向后和向前循环。跳数越多，路径就越“短”。

这与算法无关，与无法回答这样的问题有关。

编辑 :

上述声明假定双向链接。如果没有整体负权重的周期，你就没有办法永远循环，获得报酬。

在这种情况下，Dijkstra 算法可能仍然失败:

考虑两条路径:

在穿过权重为 -25 的最终边之前，成本为 100 的最佳路径，总共为 75，并且

没有负加权边的次优路径，总成本为 90。

Dijkstra 算法将首先调查次优路径，并在找到时宣布自己已完成。它永远不会跟进比找到的第一个解决方案更糟糕的子路径