如果有向图仅包含一个负权重边且不包含负权重循环，那么Dijkstra算法是否有效？
Dijkstra算法适用于只有一条负权边吗？
13
- jsh6303
2
可能是 Dijkstra算法中使用负权重的重复问题。 - Jerry Coffin
3@JerryCoffin- 我不认为这是一个重复的问题。这个问题讨论了Dijkstra算法在一组非常具体的负边界限制下的应用，而原始问题则是关于为什么Dijkstra算法不能处理带有一般负边的图形的问题。 - templatetypedef
9个回答
16
不，Dijkstra算法是一种贪心算法。它假设路径权重严格递增。
考虑以下图形。S→A→E是最优的，但Dijkstra算法将返回S→B→E。
- John Kugelman
5
我认为这个反例是错误的 -
A 顶点将会最后弹出，然后算法会放松边缘 A-E，因此选定的路径将会是预期的 S->A->E。 - Elimination1一旦找到S→B→E，Dijkstra算法就不会继续搜索。这就是贪心的含义。它采用找到的第一个解决方案，不寻找其他更好的解决方案。当所有的权重都是非负数时，就不会有更好的了。 - John Kugelman
据我所知不正确：我审查了CLRS书中提出的算法。当优先队列为空时，该算法停止。因此，当
A从优先队列中弹出时，我们将像我上面说的那样松弛边缘A->E。 - Elimination1如果你想要找到图中从S到每个节点的最短路径，你需要处理整个队列。如果你只关心从S到E的路径，则在找到E后就可以停止搜索了。 - John Kugelman
也许吧，但经典算法形式（即CLRS中的算法）会在p-queue为空时停止。 - Elimination
2
不行。考虑以下简单反例，只有3个节点，
算法首先会固定
S（开始），A和B。w(S, A) = 1
w(S, B) = 2
w(B, A) = -2
算法首先会固定
A的距离（代价为1），但是通过B去那里更便宜（代价为0）。- Vincent van der Weele
2
我认为这是错误的；
B 顶点将会最后从优先队列中弹出，然后我们将放松边 B->A。请注意，算法在优先队列为空时停止！ - EliminationDijkstra算法生成一棵生成树。从S到A的最短路径是
S->B->A（权重为0）。从S到B的最短路径是S->A->B（权重为-1）。这些路径不能同时存在于生成树中，因为那就不是一棵树了。 - Vincent van der Weele2
由于Dijkstra算法是贪心算法，不能处理带有负权重的情况。您需要使用其他算法，如Bellman-Ford算法来解决这个问题。
但是，如果您仍然想使用Dijkstra算法，有一个已知的方法。在这种方法中，您需要重新分配成本，以使所有成本变为正数。
具体步骤如下：
假设存在从u到v的边缘。该边缘的成本为cost(u,v)。
u(d(u))------>v(d(v))
定义：
new_cost(u,v) = cost(u,v) + d(u) - d(v)
这是有保证为正数的，因为，
d(v) < d(u) + cost(u,v)
现在，我们可以正常运用Dijkstra算法，唯一的区别是新路径的成本，它将是（假设路径在s'和t'之间）。请注意保留HTML标签。
= original cost of the same path + d(s') - d(t')
- Ranveer
2
你能描述一下你从哪篇科学论文或者哪个作者那里获得了重新设计成本的信息吗？因为我听到一位专门研究Dijkstra算法的科学家说，很多人尝试使用Dijkstra算法来处理负权重问题，但实际上没有人成功过。 - AlexWien
我没有在负权重上使用Dijkstra算法，这是不可能的。我只是使用数学运算来改变成本本身。如果您仔细观察，新旧成本只会相差一个常数。 - Ranveer
2
并不是一定能。在这篇早先的回答中，我给出了一个没有负环但有一个负边的图的例子，Dijkstra算法不能得出正确的答案。因此，在这种情况下Dijkstra算法并不总是有效的。
希望这能帮到您！
- templatetypedef
2
不，Dijkstra算法是一种贪心算法。一旦它添加了一条边，就不会再回头看。
- Vallabh Patade
2
你不能直接将Dijkstra算法应用于带有负边的图，正如其他答案中正确指出的那样。
如果原始图中没有负环，则可以通过重新加权图边来实现。这是Johnson算法中使用的相同技术，在其中首先运行一次Bellman-Ford算法以获取每个顶点
Coursera 算法课程中的第XV节比我解释得更好。
应用这种技术解决单源最短路径问题的唯一问题是，使用Bellman-Ford重新赋权需要O(mn)时间，比Dijkstra的O(m log(n))慢。因此，最好只在原始图形上运行Bellman-Ford算法。
如果原始图中没有负环，则可以通过重新加权图边来实现。这是Johnson算法中使用的相同技术，在其中首先运行一次Bellman-Ford算法以获取每个顶点
v的权重h(v)。然后将每个边w(u,v)修改为w(u,v) + h(u) - h(v)，这保证是正数，因此您最终得到一个仅包含正边的新图，您可以在上面运行Dijkstra算法。Coursera 算法课程中的第XV节比我解释得更好。
应用这种技术解决单源最短路径问题的唯一问题是，使用Bellman-Ford重新赋权需要O(mn)时间，比Dijkstra的O(m log(n))慢。因此，最好只在原始图形上运行Bellman-Ford算法。
- Daniel
2
只要从具有负权出边的节点开始，Dijkstra算法即可处理单个负权边。
通过从图中最小值的边开始，你不能再通过考虑其他边权重来减少总成本（这就是Dijkstra算法的工作方式）。
- EhH17
1
不，Dijkstra算法众所周知不能处理负权重。如果需要处理负权重，请使用Bellman-Ford算法。
- AlexWien
0
为什么Dijkstra算法可能失败，很简单：
因为最短路径应该是：distance(s, vi) ≤ distance(s, vk)
例如，我们有这个图：
A---->B 距离2 B--->C 距离-4 此时条件不满足 因为A到B的距离 > B到C的距离
- Ach Ref
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接