引用Stackoverflow上的一个问题

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

From the website:

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.

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:

Assume the edges are directed from left to right as in your example,

Your algorithm will work as follows:

1. First, you set d(A) to zero and the other distances to infinity.
2. You then expand out node A, setting d(B) to 1, d(C) to zero, 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.

Notice that at the end of this, though, that d(C) is still 0, even though the shortest path to C has length -200. Your algorithm thus fails to accurately compute distances in some cases. 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求出来了。

题主的例子，最后全部点都是橙色(算法运行结果正确)：

​

高票的例子，最后有一个点红色(那个点没被正确更新，算法运行结果错误)：

​

Post modified: 2019-10-18