Negative edges
Task number: 4163
Construct an example of a graph with one edge of negative length on which Dijkstra’s algorithm fails.
In which part of the proof of the correctness of Dijkstra’s algorithm was the assumption of non-negative edge lengths needed?
Solution
If we allow negative edge lengths, the triangular inequality may not apply.
Take, for example, \( G = C_3 \) with lengths \( l (u, v) = 1 \), \( l (u, w) = 2 \), \( l (v, w) = - 2 \).
Dikstra’s algorithm preferably takes \( v \) and reports that \( dist (u, v) = 1 \), while the path through \( w \) would have a total length of \( 0 \).
