Dijkstra’s algorithm fails with negative weights because it is a greedy algorithm that locks in the shortest path to a node the very first time it visits (or “settles”) that node. It relies on a foundational mathematical assumption: adding an edge to a path can never make the path shorter. When negative weights are introduced, this assumption breaks completely, causing the algorithm to miss optimal paths or get stuck in infinite loops. 1. The Core Greedy Assumption
Dijkstra’s algorithm manages a priority queue of unvisited nodes based on their current tentative distance from the source.
In each iteration, it extracts the node with the absolute minimum tentative distance. The algorithm marks this node as “visited” (or finalized).
It assumes that because all edge weights are positive, any alternate route discovered later down the line will only add weight and can never beat the path just locked in.
When negative weights exist, a longer, more expensive path can suddenly become much cheaper later on due to a negative edge, rendering the previously finalized “shortest path” incorrect. 2. A Concrete Counter-Example
Consider a simple directed graph with three nodes: A (Source), B, and C. Edge A → B: weight = 5 Edge A → C: weight = 6 Edge C → B: weight = -3 5 A —-> B^ 6 / -3 v / C How Dijkstra Processes This Graph:
Initialization: Start at A. Distance to A = 0, B = ∞, C = ∞.
First Iteration: From A, update neighbors. Distance to B becomes 5; distance to C becomes 6.
The Greedy Choice: The algorithm looks at the unvisited nodes (B with cost 5, C with cost 6) and greedily extracts B because 5 is less than 6. Node B is now marked visited/finalized with a shortest path of 5.
Second Iteration: The algorithm extracts C (cost 6). It looks at the edge C → B (weight -3). It notes that traveling A → C → B would cost 6 + (-3) = 3.
The Failure: Because B was already finalized in step 3, standard Dijkstra’s algorithm ignores this update or fails to correctly re-evaluate paths leading out of B. It incorrectly concludes that the shortest path to B is 5, missing the true shortest path of 3. 3. The Fatal Trap: Negative Weight Cycles
If a graph contains a negative weight cycle (a loop where the sum of the edge weights is less than zero), the concept of a “shortest path” completely collapses.
Every time an algorithm loops through a negative cycle, the total path cost decreases toward negative infinity (-∞). Standard implementations of Dijkstra’s algorithm will either yield completely broken results or get trapped in an infinite loop if the visited check is removed to fix the negative edge issue. 4. Why “Just Adding a Constant” Doesn’t Work
A common misconception is that you can fix negative weights by finding the most negative edge, adding its absolute value to every edge in the graph to make all weights positive, and running Dijkstra’s algorithm. This fails because it disproportionately penalizes paths with more edges.
Leave a Reply