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

Question

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

Answer 1

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

如果两个节点之间的权重为负值，那么“最短路径”就是在这两个节点之间来回循环。跳数越多，路径越“短”。

这与算法无关，而是与无法回答这样一个问题有关。

编辑

上面的权利要求假设双向链路。如果没有总负权重的周期，你就没有办法永远循环，得到报酬。

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

考虑两条路径：

• 是在穿过权重为-25的最终边之前累积成本为100的最优路径，总成本为75；
• 是一条没有负权重边的次优路径，总成本为90。

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

Answer 2

我将给你举一个反例。考虑下面的图

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

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

1. 将A标记为已访问，并以最小距离将顶点B和C添加到queue
2. Fetch from queue顶点。is B
3. Mark B as visited and add vertex D to queue.
4. Fetch from queue。Not it is vertex D.
5. Mark D as visited

(不是访问过的顶点对象)

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

Answer 3

想象一下，你有一个有向图，其中有一个有向圈，它周围的总“距离”是一个负权重。如果在从起点到终点的过程中，你可以穿过那个有向循环，你可以简单地绕着这个有向循环转任意次。

这意味着你可以让你在图中的路径有一个无限负的距离(或者有效地这样做)。

然而，只要你的图周围没有有向环，你就可以使用Dijkstra算法而不会有任何问题。

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