[Math] Tricking Dijkstra’s Algorithm for negative weights

graph theory

I'm doing this only for educationnal purposes, so when i was studying at college (i was computer science student) we've studied Dijkstra's algorithm for shortest path and our teacher said to us that : "Dijkstra's algorithm doesn't work with graphs which contains negative weight, and explained it to us", i really don't remeber the explication, and i forget a little about the algorithm, but now i think for making the Dijkstra's algorithm working for graphes with negative weights.

The trick is easy, Dijkstra algorithm doesn't work for negative weights, so we will force every weight to be in positive, and that by adding to each edge, the inverse of min negative weight, by that we have forced the graph to contains only positive weights, then we proceced with Dijkstra's algorithm, at the end we substract the value which we added it.

It seems to me as it works because we have just did added to every edge the same value, then at the end we substract it.

an exemple :

Original graph

the shortest path from A to D is = A -> C -> B -> D, the weight is = -2.

So now, there's a negative wheight, we will take the min weight from the graph and add the inverse of it to all edges.

Modified graph

the shortest path from A to D is = A -> C -> B -> D, the weight is = 7 – 9 = -2.
we should substract 9 from 7 because we have traveled 3 edges and for each edge we have added 3.

I think this trick should still produce the shortest path for negative weights, because we just added the same value to each edge, the as equations, when we add a value to an equation, it stills valid 🙂

Best Answer

It doesn't because as @steve-kass said in the comments, the shortest path may have more edges than other paths, thus when adding weight to every edge, there will be more total weight added to the shortest path than to other paths that use fewer edges.

Look at this example:

     +1
   D <- C
   ^    ^
+2 |    |-1
   A -> B
     +1

Let's compare the paths for going from A to D: AD versus ABCD. AD uses only one edge with cost +2 while ABCD uses three edges with total cost +1. ABCD is optimal.

However, when we increase the weight of all edges to make them non-negative, AD becomes shorter than ABCD because ABCD uses many more edges than AD:

     +2
   D <- C
   ^    ^
+3 |    | 0
   A -> B
     +2
Related Question