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

Question

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

Answer 1

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

如果两个节点之间存在负权重，则“最短路径”是在这两个节点之间永远来回循环。跃点越多，路径就越“短”。

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

编辑：

上述声明假设双向链接。如果没有具有总体负权重的周期，那么您就没有办法永远循环，获得报酬。

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

考虑两条路径：

• 一条成本为 100 的最优路径，然后越过权重为 -25 的最终边，总共为 75，以及
• 一条没有负加权边的次优路径，总成本为 90。

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

Answer 2

我给你一个反例。考虑下图

http://img853.imageshack.us/img853/7318/3fk8.png

假设您从顶点开始，A并且想要到 的最短路径D。Dijkstra 的算法将执行以下步骤：

1. 标记A为已访问并添加顶点B并C排队
2. 以最小距离从队列顶点获取。这是B
3. 标记B为已访问并将顶点添加D到队列中。
4. 从队列中获取。不是它是顶点D。
5. 标记D为已访问

ADijkstra 说从to 到的最短路径的D长度为 2，但这显然不是真的。

Answer 3

想象一下，你有一个有向图，它有一个有向循环，而围绕它的总“距离”是一个负权重。如果在从起点到终点的途中，您可以通过该有向循环，则您可以简单地绕着该有向循环任意次数。

这意味着您可以使您在图表上的路径具有无限负距离（或实际上如此）。

但是，只要您的图形周围没有有向循环，您就可以使用 Dijkstra 算法而不会发生任何爆炸。

话虽如此，如果你有一个负权重的图表，你可以使用Belman-Ford算法。然而，由于该算法的通用性，它有点慢。Bellman-Ford 算法需要 O(V·E)，而 Dijkstra 算法需要 O(E + VlogV) 时间