Why does Dijkstra's algorithm fail when an edge has a negative weight, and what do you use instead?
Dijkstra's algorithm finishes a node as soon as it has the smallest distance. That is only safe when every edge weight is positive, because a finished node can never be improved later.
So what goes wrong with a negative edge? Here is the example.
the graph the edges and their weights
A -> B A to B costs 4
A -> C A to C costs 5
C -> B C to B costs -10
the shortest route from A to B
the direct route costs 4
the route through C costs 5 + (-10) = -5
so the route through C is better
And Dijkstra gets this wrong. It works out that A has a distance of zero and C has a distance of five, and then it works out that B has a distance of four. Then it takes B out of the heap and finishes it, because four is smaller than five. But later it reaches C and finds a route to B that costs minus five, and B was already finished.
And that is the whole problem. Dijkstra assumes that once a node has the smallest distance it cannot be beaten, and that assumption is only true when no edge goes backwards in cost.
the assumption Dijkstra Bellman-Ford
-------------------- ---------- ---------------------------
the weights positive yes yes
a negative edge no yes
the time O((n+m)logn) O(n*m)
And what do you use instead? Bellman-Ford. It relaxes every edge over and over, and it does that n minus one times. That way a route that goes through many nodes in the wrong order still gets found, because each round lets the distance travel one more node along the route.
And Bellman-Ford can also tell you whether there is a negative cycle, which is a cycle whose total weight is less than zero. In that case you can go round the cycle for ever and the distance keeps going down, so there is no shortest path at all.
So the rule to remember is this. Dijkstra for positive weights, and Bellman-Ford when there might be a negative edge.
The last question in this topic shows the code.