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?
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