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?

Willable

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

Chromate

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!

Divest

This doesn't answer the question, but is rather discussing a different way to modify Dijkstra in order to make it terminate with non-negative edges. The question was about a specific modification that makes it not only terminate, but work (as long as the result is defined, of course). – Fowkes

@mastov, this answer first tells the OP that his modification is not enough for the algorithm to terminate (because of negative loops) and completes the OP's own suggestion by mentioning what can be added to make it terminate. It then proceeds to tell why that's not a good idea and how the optimal solution may not be found anyway. – Divest

In other words, the specific modification in the question neither terminates nor works (in general of course). – Divest

It both terminates and works, iff there is a solution. – Fowkes

@mastov, ok, but what's the point? First of all, it's going to lose its nice execution order (even for all positive graphs it will be slower, or maybe you want to put an if before that checks whether a negative edge exists at all?). Second, you are not checking before hand if there is a solution or not. That means that if there is not a solution, you are stuck in an infinite loop. May I remind you that a procedure that doesn't necessarily terminate is not an algorithm by definition? Besides, a procedure that may never terminate is the last thing you would ever want to use on a graph. – Divest

1. No, you are wrong. It won't be slower for positive graphs. There the execution order is the same, as shown by Cherish's answer. 2. About your theoretical argument: An algorithm doesn't need to terminate on invalid inputs. 3. About the practical use: There are cases in which this algorithm is in practice faster than algorithms with better worst-case performance (like Bellman-Ford). There are many examples of graphs, in which you know beforehand that they won't contain negative cycles. You can even implement a safety net very easily, by limiting the number of iterations, just to be sure. – Fowkes

@mastov, first of all, feel free to write your own answer. By the way, limiting the number of iterations is not how you do things, because you either underestimate the number and fail on valid input or overestimate and waste time. If you want to be sure, you don't traverse any node or edge twice which is exactly what I wrote in the beginning of my answer. – Divest

Also, let's not lose sight at what Dijkstra's algorithm is. It's to find shortest path on graphs with non-negative edges. Even if the big O of the algorithm doesn't change for its original use, it's big Omega changes and that means longer execution time in practice. That's why you don't see people modify the algorithm in this way, it's as simple as that. What's more, instead of half-solving the problem of negative edges with this solution, there are actual proper solutions, like Johnson's algorithm. – Divest

I did write my own answer yesterday. But now, while skimming through others, I found that the most-upvoted answer contains statements I consider plainly wrong, which I think should be noted. It disqualifies the suggested correct algorithm as wrong, when it isn't. It is your modification that makes it wrong, for fixing termination in a case in which the problem itself isn't defined. – Fowkes

Btw., as I said, limiting the iteration isn't even necessary. The algorithm is correct without it. I just suggested this as mitigation for the ugly non-termination that bothered you. It's not part of the regular control flow, just a safety net in case the user of the algorithm got it wrong. In the case of a correct input, the safety net doesn't do anything. – Fowkes

Of course, in general (worst-case complexity) there are more efficient algorithms than this. But the algorithm is correct (other than stated in your answer) and is even practical in special cases. – Fowkes

@mastov, I just read your answer. So first you assume two properties and based on that say the OP's modification to Dijkstra's algorithm works. So I hope you agree that without those assumptions it doesn't work? Doesn't that entitle me to say without assuming anything that the OP's modification doesn't work? – Divest

Then you go on to say that generally the worst case execution can become horrible and warn the OP. How is that different from what I've been saying all this time? It looks like the only difference there is to what you and I say is that I didn't say "in some situation with certain assumptions your modification is actually good". So what if I didn't say it? It doesn't make my answer wrong. At most, it could make it incomplete. – Divest

I tried to be very explicit because this is a question-answer forum. Usually I'd have assumed that implicitly, without mentioning it. I think limiting your algorithm to a problem that's actually defined (you provided a good example for one that isn't defined) is obvious. And modifying an operation that became undefined to the most similar operation isn't exactly a huge leap either. I don't agree that the algorithm fails without my assumption of a defined problem. It doesn't work either. Because in order to tell, if an algorithm work or not, you need a properly defined problem. – Fowkes

What's bothering me is that you are saying that the algorithm doesn't work, when it fact it gives the correct answer for every case that's defined. Then you suggest a modification that breaks that correctness. – Fowkes

@mastov, what you are saying is analogous to this: Question: The summation algorithm has this carry thing. Why not just drop it? Wouldn't it be faster? My answer: no because then your suggestion fails to compute 64+78. Your comment: if no two digits have sum bigger than nine, that algorithm is actually good and correct. In other words, it's correct for every case that's defined. – Divest

Let us continue this discussion in chat. – Divest

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

Macaco

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.

Dympha

The algorithm with the stated modification won't ever give a wrong answer. It gives the right answer, whenever it exists (in your case the problem of shortest paths itself is undefined). Otherwise it will not terminate (which can be fixed easily by an upper bound for the iterations and throwing an exception). – Fowkes

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.

Fowkes

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.

Harping