Why Does Dijkstra's Algorithm Fail With Negative Weights?

Dijkstra's shortest-path algorithm fails on graphs with negative edge weights because it relies on a greedy assumption that once a vertex is visited, its shortest path has been permanently found. When negative weights are present, a longer path in terms of edge count can have a smaller total weight, invalidating this greedy choice and causing the algorithm to return incorrect distances.

The Greedy Assumption Behind Dijkstra's Algorithm

Dijkstra's algorithm maintains a set of visited vertices whose shortest distances from the source vertex \(s\) are considered final. At each step, it selects the unvisited vertex \(u\) with the smallest tentative distance \(d[u]\), marks it as visited, and relaxes all outgoing edges \((u, v)\) with weight \(w(u, v)\) using the update:

\[d[v] = \min(d[v], d[u] + w(u, v))\]

This approach works when all edge weights are non-negative (\(w(u, v) \ge 0\)) because adding any edge to a path can never decrease its total weight. Therefore, any path from \(s\) to \(u\) that passes through other unvisited vertices must have a total weight at least as large as \(d[u]\), guaranteeing that \(d[u]\) is optimal the moment \(u\) is selected.

How Negative Edge Weights Break Optimal Substructure

When a graph contains negative edge weights, the monotonicity property no longer holds. A path that initially appears more expensive can become cheaper later by traversing a negative-weight edge.

Consider a simple directed graph with three vertices \(A\), \(B\), and \(C\), where \(A\) is the source:

  • Edge \((A, B)\) has weight \(2\)
  • Edge \((A, C)\) has weight \(5\)
  • Edge \((C, B)\) has weight \(-4\)
  1. Dijkstra's algorithm initializes \(d[A] = 0\), \(d[B] = \infty\), and \(d[C] = \infty\).
  2. From \(A\), it updates \(d[B] = 2\) and \(d[C] = 5\).
  3. It selects \(B\) next because \(2 < 5\), and marks \(B\) as visited with a final distance of \(2\).
  4. Next, it visits \(C\) with distance \(5\) and relaxes edge \((C, B)\), which yields \(5 + (-4) = 1\).

Because \(B\) was already marked as visited, standard implementations of Dijkstra's algorithm will not re-evaluate \(B\), leaving \(d[B] = 2\) instead of the true shortest distance of \(1\). Even if re-evaluation were allowed, the algorithm would lose its polynomial time guarantee and could loop indefinitely if negative cycles exist.

Negative Cycles and Undefined Shortest Paths

A negative cycle is a cycle whose edge weights sum to a negative value. If a graph contains a negative cycle reachable from the source, the concept of a shortest path becomes undefined because traversing the cycle repeatedly reduces the total path weight without bound toward \(-\infty\). Dijkstra's algorithm cannot detect negative cycles and will either terminate with wrong answers or fail to terminate if modified to re-visit vertices.

Alternatives for Graphs With Negative Weights

When negative edge weights are present, classical computing relies on algorithms that do not make irreversible greedy choices:

  • Bellman-Ford Algorithm: Relaxes all edges \(|V| - 1\) times, where \(|V|\) is the number of vertices. It correctly computes shortest paths with negative weights in \(O(|V||E|)\) time and can detect reachable negative cycles.
  • SPFA (Shortest Path Faster Algorithm): An optimization of Bellman-Ford using a queue that performs well in practice on sparse graphs, though its worst-case complexity remains \(O(|V||E|)\).
  • Johnson's Algorithm: Combines Bellman-Ford and Dijkstra's algorithm to find all-pairs shortest paths in sparse graphs with negative weights by reweighting edges to be non-negative.