Graph Theory37 sections · 1633 units
Open in Course

When Dijkstra Fails

(Negative edge problem)

Dijkstra assumes once you process a node, you have found its shortest path. That assumption breaks with negative edges because a later path can improve an already-processed distance. Consider a graph: ABA \to B (weight 55), ACA \to C (weight 22), CBC \to B (weight 4-4). Dijkstra processes BB first with distance 55, marks it as final, and never checks the better path ACBA \to C \to B with total cost 2-2.

The greedy choice fails because processing nodes by current distance does not account for future improvements through negative edges. You need an algorithm that checks all possible paths, not the locally best ones.