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

Question

The pseudocode as 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 the relaxation is applied only on neighbors of u that have not yet been removed from Q. But if we take also neighbors of u that have been removed from Q, it seems to me that the algorithm does work with negative weights. I haven't found any instance that contradicts this claim.

So why Dijkstra's Algorithm isn't altered this way?

Answer 1

Dijkstra can afford to visit each node one and once because when it picks a new node to visit, he picks the non-visited node that has the shortest path from the root. As a consequence, he can safely assume that there is no shorter way to go to that node through another non-visited 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 chance to find a better way from A to B such as A>C>B).

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

You could of course use your suggested modification, but then you would lose the benefit of visiting each node only once ; and thus it would lose its gain of performance compared to other algorithms such as Ford-Bellman

Answer 2

You can certainly make Dijkstra's algorithm work with negative values, simply by making sure you don't traverse any node or edge twice. Here, by work, I mean terminate. The result however may not be optimal.

Dijkstra's algorithm has a greedy sense to it. Imagine the following graph:

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

If we want to go from A to B, the best path would be A-C-D-B, but Dijkstra's algorithm finds A-B. You cannot make Dijkstra's algorithm predict the future because it is a greedy algorithm. By predicting the future I mean knowing that later on, the cost of a path may be reduced. Note that this means your modification would work incorrectly if it is applied to a version of Dijkstra's algorithm that terminates as soon as the destination is seen. In the version you posted, your modification works except there are more efficient ways to handle negative edges (see comments).

As a side note, shortest path in undirected graphs with negative values or directed graphs with negative loops doesn't even make sense!

Answer 3

You have basically two options.

1. You can change algorithm as you propose. If you have directed graph with no negative cycle, then this is a correct algorithm, but it can be really slow (because you will visit each node many times). I think that there is a case when this algorithm has exponencial time complexity.

2. You can alter edges costs by using potencials. Every vertex has some potencial h(v) and weight for edge u->v will be w(u,v) + h(u) - h(v). Note that this doesn't affect which path between given two vertices (s, t) is the shortest one only its cost is altered by h(s) - h(t). But you need to calculate potencials. Good way of doing that is suggested here: http://en.wikipedia.org/wiki/Johnson's_algorithm

Answer 4

No, not possible as stated. The algorithm doesn't make sense with negative weights, unless you severely constrain the graph type supplied.

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

There no longer exists a shortest path between A and C now, and you could always make a shorter one by going back and forth between A and B one more time.

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

Answer 5

Yes, your modification would work under 2 assumptions that you haven't mentioned, but I guess were implied:

1. Shortest paths have to actually be defined in your input graph. If you drop the restriction about non-negative weights, you must at least demand that there are no cycles with negative weight.
2. The "decrease-key v in Q" operation in line 19 doesn't really make sense on nodes v that are not in Q. But, of course, you can re-add them to Q with the new value.

However, you'd loose an important feature of the Dijkstra algorithm: Its good worst-case asymptotic performance. The off-the-shelf Dijkstra guarantees good performance because it visits every node and every edge at most once. With your change included, nodes that have already been removed can get re-added to the priority queue and possibly large parts of the graph have to be visited over and over again. In the worst case you have to perform as many relaxations as, for example, the Bellman-Ford algorithm, but you have the additional overhead of the priority queue. That makes your worst-case performance worse than Bellman-Ford, which is therefore preferred for graphs with negative edges.

This doesn't mean that your modified Dijkstra isn't useful. It can perform much better than Bellman-Ford, if you have very few negative edges and/or if those negative edges are separated from the rest of the graph by expensive paths. But be prepared for a quite bad worst-case performance.

Answer 6

Well, to just relax the already visited Nodes in the modified version of Dijkstra is not enough(and it would give you a wrong answer in graph containing negative edges). Moreover, you need to put ANY relaxed edge into your container(for instance, priority queue or just queue). Therefore, you could revise code from the line 19 as:

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

In this case, your algorithm could work. Furthermore, the efficiency for the modified version of Dijkstra will not decrease for positive weighted graph. This could be easily proved because this is naturally a greedy algorithm.

However, for graphs containing negative edges, the new algorithm might become slow in term of theory analysis, but it will work well in practice.

Actually, you could take a look at an algorithm named SPFA(Shortest Path Faster Algorithm) published by Dingfan Duan in China(1994). Lots of OIer(Olympic of Info) know this algorithm for it sometimes might beat Dijkstra.