algorithm - 使用 Dijkstra 算法的负权重

Question

我想了解为什么 Dijkstra 算法不适用于负权重。在 Shortest Paths 上阅读示例，我试图弄清楚以下情况:

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

来自网站:

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 上运行 relax，请参阅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(< em>D) 到 99.
3. 接下来，您展开C，没有任何净变化。
4. 然后展开 B，但没有任何效果。
5. 最后，您展开 D，将 d(B) 更改为 -201。

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

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