Negative weights using Dijkstra's Algorithm

Question

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)
}

Thanks,

Meir

• Nick Johnson: Pathfinding in general with negative edge weights is extremely difficult. No matter what route you find, there's always the possibility of an arbitrarily long route with an arbitrarily large negative edge weight somewhere along it. I wouldn't be surprised if it's NP complete.
• goelakash: For anyone else having this doubt, you can find shortest path in a graph GIVEN that it doesn't have negative weight cycles. The above algorithm would work if the Relax function returned a "true" value when relax was actually successful, in which case, the adjacent vertex "v" would be enqueued in the priority queue if not present, or updated if already present. This means that visited nodes can again be added to the priority queue as they keep getting relaxed.

Answer 1

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:

A directed graph with four nodes, A, B, C, and D. Node A has an edge to B of cost 1, an edge to C of cost 0, and an edge to D of cost 99. Node B has an edge to cost 1 to node C. Node D has an edge of cost -300 to node B.

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.

• blubb: To add to your excellent answer: Dijkstra being a greedy algorithm is the reason for its short-sighted choice.
• Nate: I would like to point out that, technically, all paths in this graph have a cost of negative infinity courtesy of the negative cycle A,D,B,A.
• templatetypedef: @Nate- To clarify, all the edges in the graph are directed from left to right. It was kinda hard to render arrows in my high-quality ASCII art. :-)
• Chiara Coetzee: For those who haven't seen graphs with negative edges before, I find a useful interpretation of this graph to be a network of toll roads, where the edge weights give the toll you pay. The -300 road is a crazy backwards toll road where they give you 300ドル instead.
• templatetypedef: @SchwitJanwityanujit- This is how Dijkstra's algorithm works. The algorithm does not explore paths, but instead works by processing nodes. Each node is processed exactly once, so as soon as we process the B node and get that its distance is 1, we will never revisit the node B or attempt to update its distance.

Answer 2

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.

• Gassa: 2. It is not clear why you think the time would me "more like Bellman-Ford" and not exponential (which is worse than Bellman-Ford). Do you have a concrete algorithm and a proof in mind?
• infty10000101: To 1.: as you can use exactly the same implementation of dijkstra with the mentioned stop criterion, that stops when a the queue runs empty (see pseudocode in original question), it is still dijkstras algorithm for shortest paths, even though it behaves differently settling nodes several times (label correcting).
• infty10000101: To 2.: That was just a guess so I'm going to delete that. I' think you're right with the exponential time, as there are exponentially many paths, which have to be explored.
• tbuglc: If you apply label correcting, it’s not longer a shortest path but probably a shortest trail by definition or I’m wrong 🤔

Answer 3

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.

• banna: I am thinking about the time complexity for version 3 that handles negative weights (If we are sure there are no negative cycles). Shouldn’t it be O(V * E)?
• Hoang Dao: Interesting, but I believe the version 3 is no more Dijkstra, it's actually SPFA (en.wikipedia.org/wiki/Shortest_path_faster_algorithm) which is a modification/optimization of Bellman-Ford (since it follows Dijkstra's idea to minimize the number of relax steps that Bellman has). Dijkstra assumes that any path originating from one node always lead to a greater distance (positive weight edge), that's why it doesn't need to recalculate when a node is visited/closed, and that make it faster than the original Bellman-Ford algorithm.

Answer 4

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.

• prusswan: Also, there is no need to modify the vertex without negative weight edges, which completely breaks the assumption that path costs can only increase with repeated edges
• amit: this assumption is exactly what allows us to use S, and 'knowing' once a vertex is in S, it will never be modified again.
• Egor Okhterov: Your last statement is wrong. The posted algorithm has time complexity O(E + VlogV) when it works on graphs without negative edges. There is no need in checking that we have already visited a node, since the fact that it has been visited guarantees the relaxation procedure won't add it one more time in the queue.

Answer 5

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.

Answer 6

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.

• amit: this is not possible, the graph is directed.
• prusswan: @amit: good point, I missed that. Time to reconsider the problem

Answer 7

"2) Can we use Dijksra’s algorithm for shortest paths for graphs with negative weights – one idea can be, calculate the minimum weight value, add a positive value (equal to absolute value of minimum weight value) to all weights and run the Dijksra’s algorithm for the modified graph. Will this algorithm work?"

This absolutely doesn't work unless all shortest paths have same length. For example given a shortest path of length two edges, and after adding absolute value to each edge, then the total path cost is increased by 2 * |max negative weight|. On the other hand another path of length three edges, so the path cost is increased by 3 * |max negative weight|. Hence, all distinct paths are increased by different amounts.

Answer 8

You can use dijkstra's algorithm with negative edges not including negative cycle, but you must allow a vertex can be visited multiple times and that version will lose it's fast time complexity.

In that case practically I've seen it's better to use SPFA algorithm which have normal queue and can handle negative edges.

Answer 9

I will be just combining all of the comments to give a better understanding of this problem.

There can be two ways of using Dijkstra's algorithms :

1. Marking the nodes that have already found the minimum distance from the source (faster algorithm since we won't be revisiting nodes whose shortest path have been found already)

2. Not marking the nodes that have already found the minimum distance from the source (a bit slower than the above)

Now the question arises, what if we don't mark the nodes so that we can find shortest path including those containing negative weights ?

The answer is simple. Consider a case when you only have negative weights in the graph:

graph containing neg. cycle)

Now, if you start from the node 0 (Source), you will have steps as (here I'm not marking the nodes):

1. 0->0 as 0, 0->1 as inf , 0->2 as inf in the beginning

2. 0->1 as -1

3. 0->2 as -5

4. 0->0 as -8 (since we are not relaxing nodes)

5. 0->1 as -9 .. and so on

This loop will go on forever, therefore Dijkstra's algorithm fails to find the minimum distance in case of negative weights (considering all the cases).

That's why Bellman Ford Algo is used to find the shortest path in case of negative weights, as it will stop the loop in case of negative cycle.

Answer 10

This is because:

1. If negative weight edges exist, the greedy strategy may fail;
2. After determining a vertex's shortest path, a shorter path might be found through negative weight edges, violating the algorithm's basic assumption: confirmed shortest paths won't be updated

For example, in the graph below, there's a negative weight edge CE with weight -13. The actual shortest path to E is 1 (shown by red arrows), but the algorithm calculates it as 10:

Error negative weight Dijkstra case

For graphs with negative weight edges, other algorithms (such as the Bellman-Ford algorithm) must be used to solve the shortest path problem.

If you want to see Dijkstra calculate the shortest path step by step, you can experience it on my Dijkstra algorithm visualization page.