Can we change Dijkstra's algorithm to work with negative weights?

Question

Pseudocode taken from Wikipedia:

function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations 3 dist[v] := infinity ; // Unknown distance function from source to v 4 previous[v] := undefined ; // Previous node in optimal path from source 5 end for ; 6 dist[source] := 0 ; // Distance from source to source 7 Q := the set of all nodes in Graph ; // All nodes in the graph are unoptimized - thus are in Q 8 while Q is not empty: // The main loop 9 u := vertex in Q with smallest distance in dist[] ; // Start node in first case 10 if dist[u] = infinity: 11 break ; // all remaining vertices are inaccessible from source 12 end if ; 13 remove u from Q ; 14 for each neighbor v of u: // where v has not yet been removed from Q. 15 alt := dist[u] + dist_between(u, v) ; 16 if alt < dist[v]: // Relax (u,v,a) 17 dist[v] := alt ; 18 previous[v] := u ; 19 decrease-key v in Q; // Reorder v in the Queue 20 end if ; 21 end for ; 22 end while ; 23 return dist[] ; 24 end Dijkstra. 

Now in line 14 we see that relaxation applies only to neighbors u that are not yet removed from Q But if we also take the neighbors from u that were removed from Q , it seems to me that the algorithm works with negative weights. I have not found a single instance that contradicts this statement.

So why is the Dijkstra Algorithm not changed this way?

Answer 1

Dijkstra can afford to visit each node once and once, because when it selects a new node to visit, it selects an unvisited node that has the shortest path from the root. As a result, he can safely assume that the shorter path to this node is through another unvisited node (because if the best way you know from A to B costs 2, and the best way from A to C costs 3, there is no way to find the best path from A to B, for example A> C> B).

If you add negative weights, you suddenly violate this assumption.

Of course, you can use the modification you proposed, but then you will lose the advantage of visiting each node only once; and thus it will lose its performance gain compared to other algorithms such as Ford-Bellman

Answer 2

You can, of course, get Dijkstra's algorithm to work with negative values, just make sure you don't cross any node or edge twice. Here, at work, I mean termination. However, the result may not be optimal.

Dijkstra's algorithm has a greedy meaning. Present the following graph:

 A --- 1 --- B | | 3 -4 | | C -- -1 --- D 

If we want to move from A to B, ACDB is the best way, but Dijkstra's algorithm will find AB. You cannot make Dijkstra's algorithm predict the future because it is a greedy algorithm. Predicting the future, I mean, knowing that in the future the cost of the path can be reduced. Please note that this means that your modification will not work correctly if it is applied to the version of Dijkstra's algorithm, which will stop as soon as the destination appears. In the version you posted, your changes work, except for more efficient ways to handle negative edges (see Comments).

As a side note, the shortest path in undirected graphs with negative values ​​or oriented graphs with negative cycles doesn't even make sense!

Answer 3

You have basically two options.

• You can change the algorithm as you suggest. If you have a directed graph without a negative loop, then this is the correct algorithm, but it can be very slow (because you will visit each node many times). I think there is a case where this algorithm has exponential time complexity.

• You can change the cost of the edges using potency. Each vertex has potential h (v), and the weight of the edge u → v is w (u, v) + h (u) - h (v). Note that this does not affect which path between the given two vertices (s, t) is the shortest, only its value changes to h (s) - h (t). But you need to calculate the potency. A good way to do this is suggested here: http://en.wikipedia.org/wiki/Johnson's_algorithm

Answer 4

No, impossible, as indicated. The algorithm does not make sense with negative weights, unless you are strongly restricting the supplied type of graph.

Suppose that a graph with nodes A, B, C and edges with weights AB = -1, BA = 0, BC = 1.

Now there is no longer a shortest path between A and C, and you can always make a shorter one by going between A and B again.

The algorithm will still work, of course, but it will give the wrong answers.

Answer 5

Yes, your modification will work under two assumptions that you did not mention, but I assume that was implied:

• The shortest paths must be defined in your input graph. If you drop the restriction on non-negative weights, you should at least require that there are no cycles with negative weights.
• The operation "decrement-key v in Q" on line 19 does not really make sense on nodes v that are not in Q. But, of course, you can re-add them to Q with a new value.

However, you will lose an important feature of Dijkstra's algorithm: its good worst-case asymptotic performance. The finished Dijkstra guarantees good performance because it visits every node and each edge no more than once. With the change enabled, nodes that have already been deleted can be re-added to the priority queue, and perhaps large portions of the schedule need to be visited again and again. In the worst case, you need to perform as many relaxations as, for example, the Bellman-Ford algorithm, but you have additional overhead for the priority queue. This makes your worst work worse than Bellman-Ford, which is why it is preferable for charts with negative edges.

This does not mean that your modified Dijkstra is not useful. It can work much better than Bellman-Ford if you have very few negative edges and / or if these negative edges are separated from the rest of the graph by expensive tracks. But be prepared for pretty bad results in the worst case.

Answer 6

Well, just relaxing the already visited nodes in a modified version of Dijkstra is not enough (and this will give you the wrong answer on the chart containing negative edges). In addition, you need to put ANY weakened edge in your container (for example, a priority queue or just a queue). Therefore, you can review the code from line 19 as:

 if v is in priority queue then decrease-key(v) else add v into priority queue 

In this case, your algorithm may work. In addition, the performance for the modified version of Dijkstra will not decrease for a positive weighted schedule. This is easy to prove because it is, naturally, a greedy algorithm.

However, for graphs containing negative edges, the new algorithm may become slow in terms of theoretical analysis, but it will work well in practice.

Actually, you can take a look at the SPFA (Fastest Fast Track Algorithm) algorithm published by Dingfan Duan in China (1994). Many OIer (Olympic of Info) know this algorithm, because sometimes it can beat Dijkstra.