Tricking Dijkstra's Algorithm for negative weights

$\begingroup$

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

$\endgroup$ 2

2 Answers

$\begingroup$

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

$\endgroup$ $\begingroup$

You could keep track of the depth of each node, then subtract (v.depth * min-weight) when comparing each distance.

I just thought about this on the spot, so I'm NOT SURE IF THIS IS CORRECT

the key steps are in 19-21

0 dijkstra-negative-weights(G(E,V))
1
1 // make every weight positive
2 min-weight = E.getMinWeight()
3 if min-weight < 0
4 for each e in E
5 e.weight -= min-weight
6
6 // initialize
7 spt-set = []
8 non-spt-set = [all v in V]
9 for each v in non-spt-set
10 v.value = infinity
11 v.depth = infinity
12 first-vertex.value = 0
13 first-vertex.depth = 0
13
14 // compute shortest path
14 while non-spt-set != empty
15 u = non-mst-set.extractMin() // by v.value
16 spt-set.add(u)
17 non-spt-set.remove(u)
18 for each v adjacent to u
19 if [(u,v).edge-weight + u.value] - [(u.depth + 1) * |min-weight|] < v.value
20 v.value = (u,v).edge-weight + u.value
21 v.depth = u.depth + 1

$\endgroup$ 4

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy