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

Solution 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:

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!

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

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

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

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

View more solutions

Comments

[amit]

this is not possible, the graph is directed.

[prusswan]

@amit: good point, I missed that. Time to reconsider the problem

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

[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. :-)

[João Portela]

@blubb from your statement it sounds as if Dijkstra algorithm gets stuck in local maxima, but the fact is, if you only have nonnegative weights that never happens. Just to clarify: for graphs with nonnegative weights Dijkstra always finds the shortest path.

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

[Evil Washing Machine]

@templatetypedef Hi, can you clarify why when you expand to D the path A-D-B-C is not relaxed, but A-D-B is?

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

[Evil Washing Machine]

@templatetypedef - ah ok :). Though can we not implement something like Bellman-Ford with FIFO Queue, where we have a table of parent pointers and shortest path, and if a node's shortest path estimate changes we go back and relax that node again?

[templatetypedef]

@SchwitJanwityanujit- That's more or less accurate for what happens in Bellman-Ford: the best distance to a node may change many times, and each time it changes new work must be done to update its cost.

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

[Alex Spencer]

Would the following be a possible solution? Step 1: Run Djikstra’s normally on graph with negative weights. Step 2: For each Negative edge E that goes into Vertex V: perform new version of dijkstra’s on V and update overall dijkstra’s if new weight is less than current weight. (performing dijkstras on least dependent negative edge FIRST). ie- if (A)----<-100>----->(B)----<-100>--->(C) perform "new dikstra" on (C) before (B).

[sarora]

The edge A-->C is not required here. Basically, any graph where the current shortest distance to a node is changed after we have used that very node to estimate the shortest distance to another node will do. In the graph above, the current shortest distance for node B changes after we use it to estimate the shortest distance to C. There is no way to ripple this change through to C in this algorithm. Note that this can only happen with negative edge weights. Also, some comments mention that Dijkstra is a greedy algorithm--however, I would not add anything to the great debate.

[Egor Okhterov]

There is no point in checking that we have already visited the node. Do you think that we need to store additional set datastructure and try to find whether we've already found the optimum for it? The implementation of Dijkstra's algorithm in the question is valid and it will correctly compute the shortest paths tree for your graph. Textbooks write about visiting each node only once to prove the worst time complexity for the graph with no negative edges, but it doesn't prevent Dijkstra from working correctly on graphs without negative circles with a different worst time complexity.

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

[templatetypedef]

@Pixar To the best of my knowledge the code given in the question will not correctly compute shortest paths. Notice that it never re-enqueues the nodes when the values change, so after the relax step updates the cost of B to be highly negative, it won't fix up the cost of nodes reachable from B. As for why to not update nodes after they're visited - you absolutely could skip this step, but this leads to a significant performance hit due to recalculating node costs repeatedly. If you do it properly, though, it can be fast. At that point it's Bellman-Ford rather than Dijkstra, though.

[Zephyr]

So Dijkstra's may work sometimes on negative edges, but will always fail on negative edge cycles right?

[templatetypedef]

@Xylene23 Not necessarily. If the graph is directed and there's no path from the start node to the negative cycle, Dijkstra's algorithm will work correctly (assuming there aren't any other negative edge weights).

[Zephyr]

Thanks. Just one more small doubt. Here at the end, we update the value D(B) = -201 when processing node D. But by that time, node B is already removed from the heap then how are you updating the value d(B) ?

[templatetypedef]

@Xylene23 It depends on the implementation. A "traditional" Dijkstra's algorithm only visits each node once, so with the OP's provided pseudocode that node won't be revisited a second time and so the ultimate distance to the goal won't be updated. You could conceivably also revisit the node a second time and repeat the exploration from there, but that breaks the runtime bound.

[Zephyr]

According to the standard Dijkstra's algorithm, node B should not be revisited or updated again back to -201 right, as the node B is removed from the priority queue. So d(B) will remain as 1 and not change to -201

[templatetypedef]

That's true, though do note that the OP's pseudocode will still relax the distance on B even after it's dequeued.

[Zephyr]

@templatetypedef Is it because here in OP's code we are checking all the vertices adjacent to the current node in the original graph and not only to the ones which are currently present in the queue when calling relax function? Which one is the standard one? I am confused

[templatetypedef]

@Xylene23 Yes, that's correct. The thing that's tricky is that this is totally dependent on how you implement Dijkstra's algorithm. You can write it in many different ways, and depending on how you do you may or may not relax vertices that are already processed. The example I included here was designed to handle the OP's code, but different examples might trip up different implementations in different ways.

[soloice]

For the pseudo code in the OP, there is no checking of visit status of each vertex. So for the graph in your answer, when d(B) is relaxed to -201 in step 4, node B will re-enque (in the Relax(u, v) function), then node B will re-deque and relax d(C) to -200, which is the correct answer.

[soloice]

As you replied in the comments, the correctness of Dijkstra's Algorithm with negative edges depends on implementation. See my answer for details.

[old_soul_on_the_run]

One reason I see Dijkstra doesn't work for negative edges is that it does not visit the already visited node again because that node has been added to the visited set. What if we do not maintain such a visited set and just keep visiting nodes as long as we get a better path?

[templatetypedef]

You can do that, but it can cause nodes to get revisited many, many times (IIRC, potentially exponentially many times!) and there wouldn't be a clear criterion for stopping the search (how do you know when you can say "okay, these distances look good enough?") That would result in a much less efficient algorithm than Dijkstra's. If you do want to use negative edge weights, look into the Bellman-Ford algorithm, which handles this case well.

[Alex Mandelias]

This explanation wouldn't work on OP's graph. If in your example node C is removed, d(B) is properly calculated to be -201 and the shortest path from A to B is correctly determined as A -> D -> B.