为什么我们不能对权重为负的图应用 Dijkstra 算法？
为什么我们不能将 Dijkstra 算法应用于具有负权重的图？
Why can't we apply Dijkstra's algorithm for a graph with negative weights?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果每次从 C 到 D 都获得报酬，那么找到从 A 到 B 的最便宜路径意味着什么？
如果两个节点之间存在负权重，则“最短路径”就是在这两个节点之间永远来回循环。跳数越多，路径就越“短”。
这与算法无关，而与无法回答这样的问题有关。
编辑：
上述声明假设双向链接。如果没有整体权重为负的循环，那么您就无法永远循环并获得报酬。
在这种情况下，Dijkstra 算法仍可能失败：
考虑两条路径：
算法将首先研究次优路径，并在找到它时宣布自己已完成。它永远不会跟踪比找到的第一个解决方案更糟糕的子路径
What does it mean to find the least expensive path from A to B, if every time you travel from C to D you get paid?
If there is a negative weight between two nodes, the "shortest path" is to loop backwards and forwards between those two nodes forever. The more hops, the "shorter" the path gets.
This is nothing to do with the algorithm, and all to do with the impossibility of answering such a question.
Edit:
The above claim assumes bidirectional links. If there is no cycles which have an overall negative weight, you do not have a way to loop around forever, being paid.
In such a case, Dijkstra's algorithm may still fail:
Consider two paths:
Dijkstra's algorithm will investigate the suboptimal path first, and will declare itself finished when it finds it. It will never follow up the subpath that is worse than the first solution found
我给你举一个反例。考虑下图
http://img853.imageshack.us/img853/7318/3fk8.png
假设您从顶点
A开始，并且想要到达D的最短路径。 Dijkstra 的算法将执行以下步骤：A标记为已访问，并将顶点B和C添加到队列BB标记为已访问并将顶点D添加到队列。D。D标记为已访问Dijkstra 说从
A到D的最短路径的长度为 2，但这显然不是真的。I will give you an counterexample. Consider following graph
http://img853.imageshack.us/img853/7318/3fk8.png
Suppose you begun in vertex
Aand you want shortest path toD. Dijkstra's algorithm would do following steps:Aas visited and add verticesBandCto queueBBas visited and add vertexDto queue.D.Das visitedDijkstra says shortest path from
AtoDhas length 2 but it is obviously not true.想象一下，其中有一个有向循环的有向图，并且围绕该循环的总“距离”是负权重。如果在从“开始”顶点到“结束”顶点的途中可以经过该有向循环，则可以简单地围绕该有向循环任意次数。
这意味着您可以使穿过图表的路径具有无限负距离（或实际上如此）。
然而，只要你的图周围没有有向循环，你就可以使用 Dijkstra 算法，而不会发生任何爆炸。
话虽这么说，如果你有一个负权重的图表，你可以使用 Belman-Ford< /a> 算法。然而，由于该算法的通用性，它的速度有点慢。 Bellman-Ford 算法需要 O(V·E)，其中 Dijkstra 算法需要 O(E + VlogV) 时间
Imagine you had a directed graph in it with a directed cycle, and the total "distance" around that was a negative weight. If on your way from the Start to the End vertex you could pass through that directed cycle, you could simply go around and around the directed cycle an arbitrary number of times.
And that means you could make you path across the graph have an infinitely negative distance (or effectively so).
However, as long as there are no directed cycles around your graph, you could get away with using Dijkstra's Algorithm without anything exploding on you.
All that being said, there if you have a graph with negative weights, you could use the Belman-Ford algorithm. Because of the generality of this algorithm, however, it is a bit slower. The Bellman-Ford algorithm takes O(V·E), where the Dijkstra's takes O(E + VlogV) time