Why doesn't Dijkstra's algorithm work for negative weight edges?

Question

Can somebody tell me why Dijkstra's algorithm for single source shortest path assumes that the edges must be non-negative.

I am talking about only edges not the negative weight cycles.

Solution 1

Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again - it assumes the path developed to this path is the shortest.

But with negative weights - it might not be true. For example:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

Dijkstra from A will first develop C, and will later fail to find A->B->C

---

EDIT a bit deeper explanation:

Note that this is important, because in each relaxation step, the algorithm assumes the "cost" to the "closed" nodes is indeed minimal, and thus the node that will next be selected is also minimal.

The idea of it is: If we have a vertex in open such that its cost is minimal - by adding any positive number to any vertex - the minimality will never change.
Without the constraint on positive numbers - the above assumption is not true.

Since we do "know" each vertex which was "closed" is minimal - we can safely do the relaxation step - without "looking back". If we do need to "look back" - Bellman-Ford offers a recursive-like (DP) solution of doing so.

Solution 2

Consider the graph shown below with the source as Vertex A. First try running Dijkstra’s algorithm yourself on it.

When I refer to Dijkstra’s algorithm in my explanation I will be talking about the Dijkstra's Algorithm as implemented below,

So starting out the values (the distance from the source to the vertex) initially assigned to each vertex are,

We first extract the vertex in Q = [A,B,C] which has smallest value, i.e. A, after which Q = [B, C]. Note A has a directed edge to B and C, also both of them are in Q, therefore we update both of those values,

Now we extract C as (2<5), now Q = [B]. Note that C is connected to nothing, so line16 loop doesn't run.

Finally we extract B, after which . Note B has a directed edge to C but C isn't present in Q therefore we again don't enter the for loop in line16,

So we end up with the distances as

Note how this is wrong as the shortest distance from A to C is 5 + -10 = -5, when you go .

So for this graph Dijkstra's Algorithm wrongly computes the distance from A to C.

This happens because Dijkstra's Algorithm does not try to find a shorter path to vertices which are already extracted from Q.

What the line16 loop is doing is taking the vertex u and saying "hey looks like we can go to v from source via u, is that (alt or alternative) distance any better than the current dist[v] we got? If so lets update dist[v]"

Note that in line16 they check all neighbors v (i.e. a directed edge exists from u to v), of u which are still in Q. In line14 they remove visited notes from Q. So if x is a visited neighbour of u, the path is not even considered as a possible shorter way from source to v.

In our example above, C was a visited neighbour of B, thus the path was not considered, leaving the current shortest path unchanged.

This is actually useful if the edge weights are all positive numbers, because then we wouldn't waste our time considering paths that can't be shorter.

So I say that when running this algorithm if x is extracted from Q before y, then its not possible to find a path - which is shorter. Let me explain this with an example,

As y has just been extracted and x had been extracted before itself, then dist[y] > dist[x] because otherwise y would have been extracted before x. (line 13 min distance first)

And as we already assumed that the edge weights are positive, i.e. length(x,y)>0. So the alternative distance (alt) via y is always sure to be greater, i.e. dist[y] + length(x,y)> dist[x]. So the value of dist[x] would not have been updated even if y was considered as a path to x, thus we conclude that it makes sense to only consider neighbors of y which are still in Q (note comment in line16)

But this thing hinges on our assumption of positive edge length, if length(u,v)<0 then depending on how negative that edge is we might replace the dist[x] after the comparison in line18.

So any dist[x] calculation we make will be incorrect if x is removed before all vertices v - such that x is a neighbour of v with negative edge connecting them - is removed.

Because each of those v vertices is the second last vertex on a potential "better" path from source to x, which is discarded by Dijkstra’s algorithm.

So in the example I gave above, the mistake was because C was removed before B was removed. While that C was a neighbour of B with a negative edge!

Just to clarify, B and C are A's neighbours. B has a single neighbour C and C has no neighbours. length(a,b) is the edge length between the vertices a and b.

Solution 3

Dijkstra's algorithm assumes paths can only become 'heavier', so that if you have a path from A to B with a weight of 3, and a path from A to C with a weight of 3, there's no way you can add an edge and get from A to B through C with a weight of less than 3.

This assumption makes the algorithm faster than algorithms that have to take negative weights into account.

Solution 4

Correctness of Dijkstra's algorithm:

We have 2 sets of vertices at any step of the algorithm. Set A consists of the vertices to which we have computed the shortest paths. Set B consists of the remaining vertices.

Inductive Hypothesis: At each step we will assume that all previous iterations are correct.

Inductive Step: When we add a vertex V to the set A and set the distance to be dist[V], we must prove that this distance is optimal. If this is not optimal then there must be some other path to the vertex V that is of shorter length.

Suppose this some other path goes through some vertex X.

Now, since dist[V] <= dist[X] , therefore any other path to V will be atleast dist[V] length, unless the graph has negative edge lengths.

Thus for dijkstra's algorithm to work, the edge weights must be non negative.

Solution 5

Try Dijkstra's algorithm on the following graph, assuming A is the source node and D is the destination, to see what is happening:

Note that you have to follow strictly the algorithm definition and you should not follow your intuition (which tells you the upper path is shorter).

The main insight here is that the algorithm only looks at all directly connected edges and it takes the smallest of these edge. The algorithm does not look ahead. You can modify this behavior , but then it is not the Dijkstra algorithm anymore.

View more solutions

Comments

[Amitk]

A correct answer with a good example would be: stackoverflow.com/questions/6799172/…

[user4157124]

Does this answer your question? Negative weights using Dijkstra's Algorithm

[Anirban Nag 'tintinmj']

Sorry but I'm not getting any error. First A->B will 1 and A->C will 100. Then B->D will 2. Then C->D will -4900. So the value of D will be -4900 same as bellman-ford. How is this not giving the right answer?

[Anirban Nag 'tintinmj']

Sorry but I'm not getting any error. First A->B will 5 and A->C will 2. Then B->C will -5. So the value of C will be -5 same as bellman-ford. How is this not giving the right answer?

[amit]

@tintinmj first, Dijkstra will "close" node A with value of 0. Then, it will look on the minimal valued node, B is 5 and C is 2. The minimal is C, so it will close C with value 2 and will never look back, when later B is closed, it cannot modify the value of C, since it is already "closed".

[Christian Schnorr]

@tintinmj If you have an outgoing edge from D, it will get visited before D's distance is decreased and hence not updated after it is. This will then result in an error for sure. If you consider D's 2 as the final distance already after scanning outgoing edges, even this graph results in an error.

[nbro]

@amit How Dijkstra's algorithm won't find the path A -> B -> C? It will first update C's distance to 2, and then B's distance to 5. Assuming that in your graph there are no outgoing edges from C, then we do nothing when visiting C (and its distance is still 2). Then we visit D's adjacent nodes, and the only adjacent node is C, whose new distance is -5. Note that in the Dijkstra's algorithm, we also keep track of the parent from which we reach (and update) the node, and doing it from C, you will get the parent B, and then A, resulting in a correct result. What am I missing?

[nbro]

@amit The problem with your reasoning (I think), and I have seen other people doing it (strangely), is that you think the algorithm will not reconsider nodes whose shortest distance has already been determined (and that we are done with), but this is not correct, and that's why we have the "relaxation" step...We iterate through all nodes of the graph, and, for each of them, we iterate through the adjacent nodes, even if any of the adjacent node might have already been removed from our min-priority queue, for example.

[nbro]

@amit Check this answer to a similar question, where the example actually makes sense: stackoverflow.com/a/6799344/3924118

[amit]

@Axl (1) There is no 'D'. (2) The algorithm does not reconsider nodes whose shortest distance was determined. See the original paper for reference. Dijsktra specicially splits the nodes to the nodes for wbLich the path o{ nrinimum lengti from P is known (set A) and others (sets B,C) . He later specifically satates: Consider all branches z connecting the node just transfeired to set A with nodes R in sets B or C, so he considers relaxing only nodes NOT in A - those who's path is not discovered yet.

[nbro]

@amit D is a typo, and I meant B.

[amit]

@Axl So, tl;dr: Dijkstra's algorithm does NOT recalculate value for any vertex who's distance was already determined. You can think of an algorithm that will - but that's not Dijkstra's Algorithm anymore.

[nbro]

@amit There are many variants of Dijkstra's algorithm, and the original one only finds the shortest path between 2 nodes, and not between a node and all other ones, which is the algorithm I am talking about, and which is more helpful.

[amit]

@Axl This is Dijkstra's Algorithm, by definition. Only difference between this and "one to all shortest path" is - you do not abort when destination is found. Also, please provide a reference for a variant that does re-open already closed nodes.

[nbro]

@amit For a reference of the algorithm I am talking about, check "Introduction to Algorithms", 3rd edition, by Cormen and friends.

[nbro]

I think that in that algorithm (it should be on chapter 24), when iterating through the adjacent nodes, it does not care if the adjacent node is still in the min priority queue or not, which is, in my opinion, what the algorithm should do to be useful.

[nbro]

Prim's algorithm for computing the minimum spanning tree is really similar to that Dijkstra's algorithm, except that it checks if the adjacent node is still on the set, which is logical, since you don't want to create a cycle.

[amit]

@Axl I see what your point when referring to this specific variant, but as said- this does not apply to "Dijkstra's Algorithm" as suggested by Dijkstra. You can claim this algorithm is useless, but 15,423 references think otherwise. Both solutions will fail (in different cases though) for negative edges, so I don't really see why one is superior to the other, except for enecdotal cases.

[nbro]

@amit I don't know well about the original algorithm except for the fact that it computed just the shortest path between 2 nodes, and that's it, but IMO, this algorithm in the book I mentioned before is more useful, even if the running time complexity might be a little bit worse...

[Pejman Poh]

@tb- Sorry for asking after such a long time but, am I on the right track here? First A->B will be 1 and A->C will be 100. Then B is explored and sets B->D to 2. Then D is explored because currently it has the shortest path back to the source? Would I be correct in saying that if B->D was 100, C would've been explored first? I understand all other examples people give except yours.

[nosense]

Like you said, the better way to solve this is to use heapq.heappush method after each comparison. We push back the updated distance into the queue. Under this condition, the Dijkstra's can work on negative weights. I tried, and the result came out as 0,5,-5

[T.Dimitrov]

@PejmanPoh from my understanding, if B->D was 100, since A->C is higher in the HeapStructure which will be used, the extract min will return A->C first which means the next found shortest path will be the path to C, after that the path from C->D which is with weight -5000 will be the obvious choice, leading us to a conclusion that the shortest path would be from A->C->D and i am pretty sure this would be the normal behaviour. So sometimes when we have negative cycles we still might get the right value for the shortest path, but definitely not always, this is an example where we will not..

[Bilal Siddiqui]

"the path source to x to u is not even considered"; did you mean source to u to x?

[Aditya P]

@slmatrix thanks for catching that, yes, I meant that the path from source to u to x, because x is a neighbor of u.

[tb-]

Well, if you have a cycle that has in sum a negative weight, then there is strictly speaking no shortest path. Because for each path P that claims to be the shortest path, you can find a path P' that is shorter by including one additional iteration of the cycle.

[tb-]

Yes, you can phrase it like that and show it by some trivial examples. However, I would rather say the Dijkstra algorithm cannot be applied for graphs with negative edge weights because the requirements are not met and if you apply it you do not know whether the result is optimal or not.

[Dakkaron]

Nope, because the optimal path would continuously jump between B and C. Imagine this: The algorithm already found this path: A B C. The current weight is 4 (5-1). Now at C it could go to D, which would give a total weight of 9. But if it instead goes back to B, it would find the path ABCBCD, which has a weight of 7, which is better. But then again, it could take ABCBCBCD, which has a weight of 5. So intrinsically, there is an endless loop if you want to find the optimal path. The optimal path with negative weights would be A (BC) D with the BC part repeated endlessly.

[Dakkaron]

With negative weights, Dijkstra might find A path, but not the optimal path (since an optimal path is not physically possible with negative weights). Thus Dijkstra (as any other pathfinding algo) cannot "work", as in return a perfect path.

[Денис Кокорев]

Actually, in the 16th line of the code there's no constraint that v should be in Q (the only 'constraint' is in the comment), so your example fails. Specifically, in your explanation the line "Note B has a directed edge to C but C isn't present in Q therefore we again don't enter the for loop in line16" is wrong, and we actually enter the loop once again and update the last edge, so that B = 1. So, the Dijkstra's algorithm runs correctly on your example.