Course contentsShow
← Computer Science
Lesson 971 of 2,87223. Shortest Path AlgorithmsFree lesson

Why Negative Edges Break Dijkstra's Algorithm

Understanding why negative edge weights violate the greedy property and cause incorrect results.

Why Negative Edges Break Dijkstra's Algorithm

You'll learn: Why Dijkstra's algorithm produces incorrect results when the graph contains negative edge weights.

The Core Problem

Dijkstra's algorithm relies on a greedy choice: once a vertex is marked as "visited" (finalized), its shortest distance is considered permanent and will never be updated again. This works beautifully when all edge weights are non-negative, but breaks down catastrophically with negative edges.

Why the Greedy Property Fails

Remember that Dijkstra's always picks the vertex with the smallest current distance to process next. It assumes that going through any other vertex first would only increase the path cost.

With negative edges, this assumption is wrong.

A Simple Example

Imagine you have:

  • Start node S
  • Nodes A and B
  • Edge S→A with weight 1
  • Edge S→B with weight 5
  • Edge A→B with weight -10

Dijkstra's would:

  1. Visit S (distance 0)
  2. Visit A next (distance 1, smallest unvisited)
  3. Mark A as finalized — this is the mistake!
  4. Later visit B with distance 5

But the actual shortest path to B is S→A→B with total cost 1 + (-10) = -9, not 5!

The problem? Dijkstra's finalized A before discovering that going through A could dramatically reduce B's distance via the negative edge.

The Broken Guarantee

The relaxation operation can't fix this once a node is finalized. Dijkstra's won't revisit A to reconsider B's distance because it greedily assumed A's path was optimal.

Key Takeaway: Negative edges break Dijkstra's greedy choice property because they allow later paths through "already finalized" vertices to be shorter than earlier direct paths—violating the algorithm's fundamental assumption.