Negative weights using Dijkstra's Algorithm

Question

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. 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.

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.

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.

Hope this helps!

Note, that Dijkstra works even for negative weights, if the Graph has no negative cycles, i.e. cycles whose summed up weight is less than zero.

Of course one might ask, why in the example made by templatetypedef Dijkstra fails even though there are no negative cycles, infact not even cycles. That is because he is using another stop criterion, that holds the algorithm as soon as the target node is reached (or all nodes have been settled once, he did not specify that exactly). In a graph without negative weights this works fine.

If one is using the alternative stop criterion, which stops the algorithm when the priority-queue (heap) runs empty (this stop criterion was also used in the question), then dijkstra will find the correct distance even for graphs with negative weights but without negative cycles.

However, in this case, the asymptotic time bound of dijkstra for graphs without negative cycles is lost. This is because a previously settled node can be reinserted into the heap when a better distance is found due to negative weights. This property is called label correcting.

TL;DR: The answer depends on your implementation. For the pseudo code you posted, it works with negative weights.

---

Variants of Dijkstra's Algorithm

The key is there are 3 kinds of implementation of Dijkstra's algorithm, but all the answers under this question ignore the differences among these variants.

1. Using a nested for-loop to relax vertices. This is the easiest way to implement Dijkstra's algorithm. The time complexity is O(V^2).
2. Priority-queue/heap based implementation + NO re-entrance allowed, where re-entrance means a relaxed vertex can be pushed into the priority-queue again to be relaxed again later.
3. Priority-queue/heap based implementation + re-entrance allowed.

Version 1 & 2 will fail on graphs with negative weights (if you get the correct answer in such cases, it is just a coincidence), but version 3 still works.

The pseudo code posted under the original problem is the version 3 above, so it works with negative weights.

Here is a good reference from Algorithm (4th edition), which says (and contains the java implementation of version 2 & 3 I mentioned above):

Q. Does Dijkstra's algorithm work with negative weights?

A. Yes and no. There are two shortest paths algorithms known as Dijkstra's algorithm, depending on whether a vertex can be enqueued on the priority queue more than once. When the weights are nonnegative, the two versions coincide (as no vertex will be enqueued more than once). The version implemented in DijkstraSP.java (which allows a vertex to be enqueued more than once) is correct in the presence of negative edge weights (but no negative cycles) but its running time is exponential in the worst case. (We note that DijkstraSP.java throws an exception if the edge-weighted digraph has an edge with a negative weight, so that a programmer is not surprised by this exponential behavior.) If we modify DijkstraSP.java so that a vertex cannot be enqueued more than once (e.g., using a marked[] array to mark those vertices that have been relaxed), then the algorithm is guaranteed to run in E log V time but it may yield incorrect results when there are edges with negative weights.

---

For more implementation details and the connection of version 3 with Bellman-Ford algorithm, please see this answer from zhihu. It is also my answer (but in Chinese). Currently I don't have time to translate it into English. I really appreciate it if someone could do this and edit this answer on stackoverflow.

you did not use S anywhere in your algorithm (besides modifying it). the idea of dijkstra is once a vertex is on S, it will not be modified ever again. in this case, once B is inside S, you will not reach it again via C.

this fact ensures the complexity of O(E+VlogV) [otherwise, you will repeat edges more then once, and vertices more then once]

in other words, the algorithm you posted, might not be in O(E+VlogV), as promised by dijkstra's algorithm.

Since Dijkstra is a Greedy approach, once a vertice is marked as visited for this loop, it would never be reevaluated again even if there's another path with less cost to reach it later on. And such issue could only happen when negative edges exist in the graph.

---

A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.

Consider what happens if you go back and forth between B and C...voila

(relevant only if the graph is not directed)

Edited: I believe the problem has to do with the fact that the path with AC* can only be better than AB with the existence of negative weight edges, so it doesn't matter where you go after AC, with the assumption of non-negative weight edges it is impossible to find a path better than AB once you chose to reach B after going AC.