Bellman-Ford — Shortest Paths with Negative Edges

The Concept

Bellman-Ford also solves the single-source shortest path problem, but unlike Dijkstra it handles graphs with negative-weight edges. The trade-off is speed: where Dijkstra runs in O((V + E) log V), Bellman-Ford runs in O(V · E) — slower, but capable of more.

The algorithm also does something Dijkstra cannot: detect negative-weight cycles. A negative cycle is a loop whose total edge weight is negative; if one exists on a path from the source to some vertex, the "shortest path" to that vertex is undefined (you could keep traversing the cycle to reduce cost indefinitely). Bellman-Ford will report that such a cycle exists.

How It Works

The core idea is relaxation: for an edge (u → v) with weight w, relaxing the edge means: "if going through u gives a shorter path to v, update v's distance."

A shortest path in a graph with V vertices has at most V − 1 edges (it cannot revisit a vertex without forming a cycle). So if we relax every edge V − 1 times, we are guaranteed to have propagated the shortest distance all the way down any simple path.

Algorithm steps:

1. Set dist[source] = 0 and dist[v] = ∞ for all other vertices.
2. Repeat V − 1 times: for every edge (u, v, w), relax it.
3. After V − 1 passes, check each edge once more. If any edge can still be relaxed, a negative cycle exists on a path reachable from the source — raise an error (or return a sentinel).

A Worked Example

Graph with 4 vertices and a negative edge:

Source: A

Pass 1:

• Relax A→B: dist[B] = 0 + 1 = 1
• Relax A→C: dist[C] = 0 + 4 = 4
• Relax B→C: dist[C] = min(4, 1 + (−2)) = min(4, −1) = −1
• Relax C→D: dist[D] = −1 + 2 = 1

Passes 2 and 3: No further improvements.

Final distances from A: B=1, C=−1, D=1. Dijkstra would never correctly compute dist[C] = −1 because it would settle C with cost 4 before discovering the shorter path through B.

Code Implementation

vertices is a list (or any iterable) of vertex identifiers; edges is a list of (u, v, w) triples. The function raises ValueError if a negative cycle is reachable from src.

Complexity Analysis

The V − 1 outer loop is the bottleneck. In the worst case (a chain graph) shortest distances propagate only one hop per pass, requiring all V − 1 passes to reach the last vertex.

Negative-Cycle Detection Explained

After V − 1 passes all shortest distances are final — unless there is a negative cycle reachable from the source. If a V-th relaxation pass still improves any distance, that improvement can only come from travelling around a negative cycle again. The extra check at the end exploits this: if any edge still relaxes, a negative cycle exists.

Note: only cycles reachable from the source are detectable this way. Isolated negative cycles elsewhere in the graph are invisible to a source-rooted Bellman-Ford run.

Dijkstra vs. Bellman-Ford

If your graph has no negative edges, prefer Dijkstra. If negative edges are possible and you also need to check for negative cycles, Bellman-Ford is the right tool.

Interactive Lab

Watch Bellman-Ford relax every edge in each of its V − 1 passes. Unlike Dijkstra, it revisits every edge regardless of whether a vertex has been "settled" — that brute-force repetition is what lets it handle negative weights.

Key Takeaways

• Relax all edges V − 1 times. After k passes, dist[v] holds the shortest path using at most k edges. V − 1 passes covers all possible simple paths.
• Handles negative edge weights. This is the fundamental advantage over Dijkstra.
• Detects negative cycles. A V-th relaxation that still improves a distance is proof that a negative cycle exists on a reachable path.
• O(V · E) time. Slower than Dijkstra's O((V + E) log V) but necessary when negative weights are present.
• Edge list representation is natural here. Unlike BFS or Dijkstra which follow neighbours, Bellman-Ford iterates over all edges each pass — an edge list [(u, v, w), ...] is the most direct representation.