使用 Dijkstra 算法的负权重 [英] Negative weights using Dijkstra's Algorithm

问题描述

我试图理解为什么 Dijkstra 的算法不适用于负权重.阅读关于最短路径的示例，我试图找出以下场景:

I am trying to understand why Dijkstra's algorithm will not work with negative weights. Reading an example on Shortest Paths, I am trying to figure out the following scenario:

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

来自网站:

假设所有的边都是从左到右的，如果我们开始对于 A，Dijkstra 算法将选择边 (A,x) 最小化d(A,A)+length(edge)，即(A,B).然后它设置 d(A,B)=2 并选择另一个边 (y,C) 最小化 d(A,y)+d(y,C)；唯一的选择是(A，C)它设置 d(A,C)=3.但它从未找到从 A 到的最短路径B，通过C，总长度为1.

Assuming the edges are all directed from left to right, If we start with A, Dijkstra's algorithm will choose the edge (A,x) minimizing d(A,A)+length(edge), namely (A,B). It then sets d(A,B)=2 and chooses another edge (y,C) minimizing d(A,y)+d(y,C); the only choice is (A,C) and it sets d(A,C)=3. But it never finds the shortest path from A to B, via C, with total length 1.

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

I can not understand why using the following implementation of Dijkstra, d[B] will not be updated to 1 (When the algorithm reaches vertex C, it will run a relax on B, see that the d[B] equals to 2, and therefore update its value to 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)
}

谢谢，

梅尔

推荐答案

你所建议的算法确实会在这个图中找到最短路径，但不是所有的图.例如，考虑这个图:

The algorithm you have suggested will indeed find the shortest path in this graph, but not all graphs in general. For example, consider this graph:

让我们跟踪算法的执行情况.

Let's trace through the execution of your algorithm.

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

1. First, you set d(A) to 0 and the other distances to ∞.
2. You then expand out node A, setting d(B) to 1, d(C) to 0, and d(D) to 99.
3. Next, you expand out C, with no net changes.
4. You then expand out B, which has no effect.
5. Finally, you expand D, which changes d(B) to -201.

请注意，虽然到 C 的最短路径长度为 -200，但在此结束时，d(C) 仍然为 0.这意味着您的算法不会计算到所有节点的正确距离.此外，即使您要存储指示如何从每个节点到起始节点 A 的返回指针，您最终也会选择从 C 返回到 C 的错误路径em>A.

Notice that at the end of this, though, that d(C) is still 0, even though the shortest path to C has length -200. This means that your algorithm doesn't compute the correct distances to all the nodes. Moreover, even if you were to store back pointers saying how to get from each node to the start node A, you'd end taking the wrong path back from C to A.

这样做的原因是 Dijkstra 的算法(和你的算法)是贪婪算法，它们假设一旦计算了到某个节点的距离，找到的距离必须是最佳距离.换句话说，该算法不允许自己获取它已扩展的节点的距离并更改该距离是多少.在负边缘的情况下，您的算法和 Dijkstra 算法可能会感到惊讶".通过看到负成本边确实会降低从起始节点到其他节点的最佳路径的成本.

The reason for this is that Dijkstra's algorithm (and your algorithm) are greedy algorithms that assume that once they've computed the distance to some node, the distance found must be the optimal distance. In other words, the algorithm doesn't allow itself to take the distance of a node it has expanded and change what that distance is. In the case of negative edges, your algorithm, and Dijkstra's algorithm, can be "surprised" by seeing a negative-cost edge that would indeed decrease the cost of the best path from the starting node to some other node.

希望这有帮助！

这篇关于使用 Dijkstra 算法的负权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！