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

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!