利用 Dijkstra 算法实现负权重

我试图理解为什么 Dijkstra 的算法在负权重情况下不起作用。阅读 最短路径上的一个例子，我试图找出以下场景:

    2
A-------B
\     /
3 \   / -2
\ /
C

网址:

假设边缘都是从左到右的，如果我们开始 与 A，Dijkstra 的算法将选择边缘(A，x)最小化 D (A，A) + 长度(边) ，即(A，B) ，然后设置 d (A，B) = 2并选择 另一个边(y，C)使 d (A，y) + d (y，C)最小; 唯一的选择是(A，C) 它设置 d (A，C) = 3。但是它从来没有找到从 A 到 B，通过 C，总长度为1。

我不明白为什么使用下面 Dijkstra 的实现，d [ B ]不会被更新到 1(当算法到达顶点 C 时，它将在 B 上运行一个弛豫，看到 d [ B ]等于 2，因此将它的值更新到 1)。

Dijkstra(G, w, s)  {
Initialize-Single-Source(G, s)
S ← Ø
Q ← V[G]//priority queue by d[v]
while Q ≠ Ø do
u ← Extract-Min(Q)
S ← S U {u}
for each vertex v in Adj[u] do
Relax(u, v)
}


Initialize-Single-Source(G, s) {
for each vertex v  V(G)
d[v] ← ∞
π[v] ← NIL
d[s] ← 0
}


Relax(u, v) {
//update only if we found a strictly shortest path
if d[v] > d[u] + w(u,v)
d[v] ← d[u] + w(u,v)
π[v] ← u
Update(Q, v)
}

谢谢,

梅尔

110324 次浏览
小开

想想如果你在 B 和 C 之间来回跑会发生什么... 瞧

(只有在图没有指向的情况下才相关)

编辑: 我认为这个问题与这样一个事实有关，即 AC * 的路径只有在负权重边缘存在的情况下才能比 AB 更好，所以你在 AC 之后去哪里并不重要，在非负权重边缘的假设下，一旦你在 AC 之后选择到达 B，就不可能找到一条比 AB 更好的路径。

小开

在算法中没有使用 S (除了修改它之外)。Dijkstra 的概念是，一旦一个顶点在 S 上，它就不会再被修改了。在这种情况下，一旦 B 在 S 里面，你就不能再通过 C 到达它了。

这个事实保证了 O (E + V logV)的复杂性[否则，边重复多次，顶点重复多次]

换句话说，你发布的算法，可能不在 O (E + V logV)中，正如 dijkstra 算法所承诺的那样。

小开
最佳答案

您所建议的算法确实可以找到此图中的最短路径，但并非所有图都是如此。例如，考虑下面这张图:

A directed graph with four nodes, A, B, C, and D. Node A has an edge to B of cost 1, an edge to C of cost 0, and an edge to D of cost 99. Node B has an edge to cost 1 to node C. Node D has an edge of cost -300 to node B.

让我们跟踪你的算法的执行过程。

  1. 首先，将 d (A)设置为0，将其他距离设置为∞。
  2. 然后展开节点 A，将 d (B)设置为1，d (C)设置为0，d (D)设置为99。
  3. 接下来，展开 C，不做任何净更改。
  4. 然后展开 B，它没有任何效果。
  5. 最后，展开 D，它将 d (B)更改为 -201。

但是请注意，尽管到达 C的最短路径的长度为 -200，但是在此结束时，d (C)仍然是0。这意味着您的算法不能计算到所有节点的正确距离。此外，即使您要存储反向指针，说明如何从每个节点到开始节点 A，您最终也会走错从 C返回到 A的路径。

这是因为 Dijkstra 的算法(以及您的算法)是 贪婪的算法，它假定一旦计算出到某个节点的距离，找到的距离必须是最佳距离。换句话说，这个算法不允许自己取一个已经展开的节点的距离并改变这个距离。在负边的情况下，您的算法和 Dijkstra 的算法可能会“惊讶”地看到一个负成本边，这确实会降低从起始节点到其他节点的最佳路径的成本。

希望这个能帮上忙！

小开

注意，Dijkstra 甚至可以工作在负权重的情况下，如果图没有负周期，即总权重小于零的周期。

当然，有人可能会问，为什么在 templatetypedef Dijkstra 的例子中，即使没有负周期，甚至没有周期，也会失败。这是因为他使用了另一个停止条件，一旦到达目标节点(或者所有节点已经安置一次，他没有确切地指定) ，该条件就保持算法不变。在没有负权重的图中，这种方法工作得很好。

如果使用替代停止准则，即在优先级队列(堆)为空时停止算法(问题中也使用了这个停止准则) ，那么 dijkstra 将找到正确的距离，即使对于负权重但没有负周期的图也是如此。

然而，在这种情况下，没有负圈的图的 dijkstra 的渐近时间界是丢失的。这是因为，当由于负权重而找到更好的距离时，可以将先前设置的节点重新插入堆中。此属性称为标签校正。

小开

因为 Dijkstra 是一种贪婪的方法，一旦一个顶点被标记为访问了这个循环，它将永远不会再次被重新计算，即使有另一条路径以较低的成本到达它。而这样的问题只有在图中存在负边时才会发生。

一个 贪婪算法，顾名思义，总是做出那个时候看起来最好的选择。假设你有一个目标函数，需要优化(最大化或最小化)在一个给定的点。确保目标函数的优化。这样 它永远不会回头，并推翻决定。

小开

“2)我们能否使用 Dijksra 算法对负权图进行最短路径处理——一种方法是，计算最小权值，给所有权值加一个正值(等于最小权值的绝对值) ，然后对修改后的图运行 Dijksra 算法。这个算法能行吗?”

除非所有的最短路径都具有相同的长度，否则这种方法绝对不起作用。例如给定一条长度为两条边的最短路径，在给每条边增加绝对值后，总路径成本增加2 * | max 负权 | 。另一方面，另一条路径的长度为三条边，因此路径代价增加了3 * | max 负权 | 。因此，所有不同的路径都会增加不同的数量。

小开

DR: 答案取决于您的实现。对于您发布的伪代码，它使用负权值。

Dijkstra 算法的变体

关键是 Dijkstra 算法有三种实现方式，但是这个问题下的所有答案都忽略了这些变体之间的差异。

  1. 使用 嵌套式 for循环放松顶点。这是实现 Dijkstra 算法最简单的方法。时间复杂度为 O (V ^ 2)。
  2. 优先级-基于队列/堆的实现 + 不允许重新进入，其中 重新进入意味着放松的顶点可以再次推入优先级队列，以便稍后再次放松。
  3. 优先级-基于队列/堆的实现 + 允许重新进入。

版本1和版本2会在负权重的图表上失败(如果在这种情况下你得到了正确的答案，这只是一个巧合) ，但是版本3仍然可以工作。

在原始问题下发布的伪代码是上面的版本3，因此它使用负权重。

下面是来自 算法(第四版)的一个很好的参考，它说(包含我上面提到的版本2和版本3的 Java 实现) :

Dijkstra 的算法对负权重有效吗？

答: 是也不是。有两种最短路径算法被称为 Dijkstra 算法，这取决于一个顶点是否可以在优先级队列上多次排队。当权重为非负值时，两个版本重合(因为没有顶点会多次排队)。Java 中实现的版本(允许一个顶点不止一次排队)在负边权重(但没有负周期)的情况下是正确的，但是在最坏的情况下它的运行时间是指数级的。(我们注意到，如果边加权有向图有一个负权的边，DijkstraSP.java 会抛出一个异常，这样程序员就不会对这种指数行为感到惊讶。)如果我们修改 DijkstraSP.java，使得一个顶点不能排队超过一次(例如，使用标记[]数组来标记那些已经放松的顶点) ，那么算法保证在 E log V 时间内运行，但是当有负权重的边时，它可能产生不正确的结果。

有关更多实现细节以及版本3与 Bellman-Ford 算法的连接，请参见 知乎的回答。这也是我的答案(但是用中文)。目前我没有时间把它翻译成英文。我真的很感激，如果有人可以这样做，并编辑这个问题的答案堆栈溢出。

小开

您可以使用 dijkstra 的算法与负边不包括负周期，但您必须允许一个顶点可以访问多次，该版本将失去它的快速时间复杂度。

在这种情况下，实际上我已经看到它更好地使用 SPFA 算法有正常的队列，可以处理负边。

小开

我将把所有的评论结合起来，以便更好地理解这个问题。

有两种方法可以使用 Dijkstra 的算法:

  1. 标记已经找到与源的最小距离的节点(更快的算法，因为我们将不再访问已经找到最短路径的节点)

  2. 没有标记已经找到与源的最小距离的节点(比上面的稍微慢一点)

现在问题来了，如果我们不标记节点，这样我们就可以找到包括 包含负重的在内的最短路径，会怎么样？

答案很简单，考虑一个情况，当你在图表中只有负权重时:

graph containing neg. cycle)

现在，如果您从节点0(来源)开始，您将有如下步骤(这里我没有标记节点) :

  1. 0-> 0作为0,0-> 1作为 inf，0-> 2作为 inf 开头

  2. 0-> 1 as-1

  3. 0-> 2 as-5

  4. 0-> 0 as-8(因为我们不是放松节点)

  5. 0-> 1 as-9. . 等等

这个循环将永远持续下去，因此 Dijkstra 的算法无法找到负权的情况下的最小距离(考虑到所有的情况)。

这就是为什么 贝尔曼 · 福特 · 阿尔戈是用来找到最短路径的情况下负权重，因为它将停止循环的情况下负周期。


提交答案