4
$\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
  • $\begingroup$ The problem with negative weights is that there might be an arbitrarily short path. Suppose in your graph that you have an edge $B \to A$ of weight $0$. Then you could come up with a path $A \to D$ with as small a total weight as you want by just taking the $A \to B \to C$ cycle (using my new edge) as many times as you want. $\endgroup$ Apr 6, 2016 at 1:27
  • 3
    $\begingroup$ The problem with this approach (which is a clever thing to try) is that while it adds the same value to each edge, it doesn’t add the same value to each path, because the possible paths from one vertex to another may not all have the same number of edges. In a graph with negative edge weights, there could even be no shortest path from $A$ to $D$, because there could be a cycle with negative length. In the example you showed, suppose $A\to B$ had initial weight $-3$ instead of $5$. Would your method work? $\endgroup$
    – Steve Kass
    Apr 6, 2016 at 1:29

2 Answers 2

6
$\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$
0
$\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
  • $\begingroup$ This is equivalent to just dealing with the original graph, which had negative edge weights, so it doesn't work. Dijkstra's algorithm works in the usual case because we never need to wait for more options to get to a node to appear, in case they're better. Here, that's not true; maybe there's a long indirect path to get to some node, which we haven't explored yet, but which will be much better because we get to subtract a much larger v.depth * min-weight. $\endgroup$ Oct 28, 2018 at 14:27
  • $\begingroup$ Also, if you don't know whether what you're writing is correct, it might be more suited to a question "Does this approach work?" than to an answer. $\endgroup$ Oct 28, 2018 at 14:28
  • $\begingroup$ thanks! I'll keep that in mind to ask a new question in situations like this. Anyways, with you previous comment, that is true. But in lines 4-5 each weight is increased by |min-weight|. Not sure if you considered that as well $\endgroup$ Oct 28, 2018 at 21:58
  • $\begingroup$ I'm taking that into account. If we increase each weight by some amount $X$, but then when we're counting the total weight of a $k$-edge path, subtract $k \cdot X$, then the end result is that all our calculations are equivalent to the algorithm where we didn't add or subtract anything at all. All the problems with that algorithm still exist here. $\endgroup$ Oct 28, 2018 at 22:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .