使用 Dijkstra 算法的负权重

Question

我试图理解为什么 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 到 A 的最短路径 B，经C，总长度1。

我不明白为什么使用以下Dijkstra实现，d[B]不会更新为1（当算法到达顶点C时，它将运行a 在 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)
}

谢谢，

梅尔

Answer 1

您建议的算法确实会找到该图中的最短路径，但并不是一般情况下的所有图。例如，考虑以下图：

让我们通过追踪执行你的算法。

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 返回到 C 的错误路径。 em>A。

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

Answer 2

请注意，如果图表没有负循环，即总权重小于零的循环，则 Dijkstra 即使对于负权重也适用。

当然，有人可能会问，为什么在 templatetypedef Dijkstra 制作的示例中，即使没有负循环，甚至没有循环，也会失败。这是因为他使用了另一个停止标准，一旦到达目标节点（或者所有节点都已解决一次，他没有具体指定），算法就保持不变。在没有负权重的图中，这效果很好。

如果使用替代停止标准，当优先级队列（堆）空时停止算法（问题中也使用了该停止标准），那么即使对于具有负权重但没有权重的图，dijkstra 也会找到正确的距离负循环。

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

Answer 3

TL;DR：答案取决于您的实施。对于您发布的伪代码，它适用于负权重。

---

Dijkstra算法的变体

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

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

版本 1 和版本 1 2 在权重为负的图上会失败（如果在这种情况下得到正确答案，那只是巧合），但版本 3 仍然有效。

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

这是来自 算法（第 4 版） 的一个很好的参考，它说（并包含 java 实现我上面提到的版本 2 和 3）：

问。 Dijkstra 算法适用于负权重吗？

A.是的，也不是。有两种称为 Dijkstra 算法的最短路径算法，具体取决于一个顶点是否可以在优先级队列中多次排队。当权重非负时，两个版本一致（因为没有顶点会被多次排队）。 DijkstraSP.java 中实现的版本（允许顶点多次入队）在存在负边权重（但没有负循环）的情况下是正确的，但在最坏的情况下其运行时间是指数级的。 （我们注意到，如果边加权有向图具有负权重的边，则 DijkstraSP.java 会抛出异常，因此程序员不会对这种指数行为感到惊讶。）如果我们修改 DijkstraSP.java 以便顶点无法入队多次（例如，使用 Marked[] 数组来标记那些已松弛的顶点），则算法保证在 E log V 时间内运行，但当存在负数边时，可能会产生不正确的结果权重。

---

更多实现细节以及版本3与Bellman-Ford算法的联系，请参见这个答案知乎。这也是我的答案（但是是中文的）。目前我没有时间将其翻译成英文。如果有人可以做到这一点并在 stackoverflow 上编辑这个答案，我真的很感激。

Answer 4

您没有在算法中的任何地方使用 S（除了修改它）。 dijkstra的思想是一旦一个顶点在S上，它就不会再被修改。在这种情况下，一旦 B 位于 S 内部，您将不会通过 C 再次到达它。

这一事实确保了 O(E+VlogV) 的复杂性 [否则，您将多次重复边，并且多次重复顶点

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

Answer 5

由于 Dijkstra 是一种贪婪方法，一旦一个顶点被标记为在此循环中已访问，即使稍后有另一条成本更低的路径可以到达它，也永远不会再次对其进行重新评估。并且只有当图中存在负边时才会发生这种问题。

---

贪婪算法，顾名思义，总是做出当时看来最好的选择。假设您有一个需要优化的目标函数（在给定点最大化或最小化）。 贪婪算法在每一步都做出贪婪的选择，以确保目标函数得到优化。 贪婪算法只有一次机会来计算最佳解决方案，因此它永远不会返回并推翻决策。

Answer 6

考虑一下如果您在 B 和 C 之间来回移动会发生什么...瞧

（仅当图形无向时才相关）

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

Answer 7

“2）我们能否使用 Dijksra 算法来计算具有负权重的图的最短路径 - 一种想法可以是，计算最小权重值，为所有权重添加一个正值（等于最小权重值的绝对值）并运行 Dijksra 算法对于修改后的图，这个算法会起作用吗？”

除非所有最短路径都具有相同的长度，否则这绝对行不通。例如，给定两条边长度的最短路径，并且在为每条边添加绝对值后，总路径成本增加 2 * |最大负权重|。另一方面，另一条路径的长度为三个边，因此路径成本增加了 3 * |最大负权重|。因此，所有不同的路径都会增加不同的量。

Answer 8

您可以使用带有不包括负循环的负边的迪杰斯特拉算法，但您必须允许一个顶点可以被多次访问，并且该版本将失去其快速时间复杂度。

在这种情况下，实际上我发现最好使用具有正常队列并且可以处理负边。

Answer 9

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

有两种使用 Dijkstra 算法的方法：

1. 标记已经找到距源最小距离的节点（更快的算法，因为我们不会重新访问已经找到最短路径的节点）

2. 不标记已经找到与源的最小距离的节点（比上面慢一点）

现在问题来了，如果我们不标记节点，这样我们就可以找到包含那些包含负数的最短路径权重？

答案很简单。考虑图中只有负权重的情况：

)

现在，如果您从节点 0（源），您的步骤如下（这里我没有标记节点）：

1. 0->0 as 0, 0->1 as inf , 0- ＞2为inf开头

2. 0->1 为 -1

3. 0->2 为 -5

4. 0->0 as -8（因为我们没有放松节点）

5. 0->1 为 -9 .. 依此类推

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

这就是为什么使用贝尔曼福特算法来寻找负权重情况下的最短路径，因为它会在负循环的情况下停止循环。