The Bellman-Ford algorithm finds shortest paths from a single source vertex to every other vertex in a weighted directed graph, and it works correctly even when edges have negative weights. It is slower than Dijkstra but handles graphs that Dijkstra cannot.

Dijkstra's algorithm greedily locks in the shortest distance to each node and never looks back, which produces wrong answers when a later edge has a negative weight that would reduce the total cost. Negative weights show up in real problems. Currency exchange is the classic example: converting USD to EUR to GBP and back to USD at a profit corresponds to a negative cycle in a weighted graph.

Bellman-Ford handles both negative edges and negative-cycle detection, which makes it the standard tool for shortest-path problems involving costs, penalties, or constraints Dijkstra cannot handle.

The core idea: relax every edge in the graph, and repeat this process V-1 times (where V is the number of vertices). After V-1 iterations, the shortest distances are guaranteed to be correct, assuming no negative cycles exist. If one more iteration still updates any distance, a negative cycle is present.

Consider a graph where Dijkstra fails but Bellman-Ford produces the right answer:

From A, the shortest path to C is A -> B -> C with cost 4 + (-5) = -1, not the direct edge A -> C with cost 10. Dijkstra would greedily finalize B at distance 4, then finalize C at distance 10 via the direct edge, and never reconsider. Bellman-Ford, by relaxing all edges repeatedly, eventually discovers the cheaper path through B.

Bellman-Ford is built on a single operation called edge relaxation, applied systematically.

Edge Relaxation

For an edge from vertex u to vertex v with weight w, relaxation checks whether going through u gives a shorter path to v than the current best:

If the condition holds, dist[v] is updated. This is the same relaxation Dijkstra uses. The difference is the order in which the two algorithms apply it: Dijkstra relaxes the edges out of one carefully chosen vertex at a time, while Bellman-Ford relaxes every edge in the graph on each pass.

The Algorithm

Why V-1 Iterations?

The shortest path from the source to any vertex has at most V-1 edges, since a simple path visits each of the V vertices at most once and therefore uses at most V-1 connections between them.

The first iteration correctly computes the shortest paths that use at most 1 edge. The second iteration produces paths with at most 2 edges. After the k-th iteration, distances reflect shortest paths using at most k edges. So after V-1 iterations, the distances cover all possible shortest paths in a graph without negative cycles.

The implementation uses an edge list representation, which is the most natural fit for Bellman-Ford since the algorithm iterates over all edges in each pass.

The time complexity is O(V * E) where V is the number of vertices and E is the number of edges. The space complexity is O(V)for the distance array.

The following trace runs Bellman-Ford on a graph with 5 vertices and two negative edges.

Edge list: (S,A,6), (S,B,7), (A,B,5), (A,C,-4), (B,C,-3), (B,D,9), (C,D,7), (A,D,8)

Initial state:

V-1 = 4 iterations are needed. In each iteration, all 8 edges are relaxed.

Iteration 1:

Iteration 2:

No distances changed in iteration 2, so the algorithm can stop early. The final shortest distances from S are: A = 6, B = 7, C = 2, D = 9.

The negative edge (A, C, -4) gives a shorter path to C through A (cost 6 - 4 = 2) than any other route. Dijkstra would happen to produce the right answer on this particular graph too, but that is coincidence: Dijkstra is not guaranteed correct in the presence of negative edges, regardless of relaxation order.

Once it pops a vertex from the priority queue it commits to that distance, and a later negative edge can invalidate the commitment. Bellman-Ford guarantees correctness on any graph without a negative cycle.

Bellman-Ford can also detect negative cycles, which are cycles whose total edge weight is negative.

Why do negative cycles matter? If a negative cycle is reachable from the source, the concept of "shortest path" becomes meaningless for any vertex reachable from that cycle. Looping around the cycle indefinitely reduces the distance without bound.

How Detection Works

One more iteration (the V-th pass) runs after the standard V-1. If any distance can still be reduced, that means a path with V or more edges is shorter, which is only possible if a negative cycle exists.

Here is a graph with a negative cycle:

The cycle A -> B -> C -> A has total weight 2 + (-3) + (-1) = -2. Each traversal of this cycle drops the total cost by 2. There is no finite shortest path to any vertex reachable from this cycle.

Implementation

The negative cycle detection code is already included in the implementation above, but here it is isolated for clarity:

Both algorithms solve the single-source shortest path problem, but they make different trade-offs.

When to use Dijkstra: The graph has no negative edge weights and speed matters. This covers most shortest-path problems.

When to use Bellman-Ford: The graph has negative edge weights, negative-cycle detection is required, or the problem constrains the number of edges in the path (like "at most K stops").

The Shortest Path Faster Algorithm (SPFA) is a queue-based optimization of Bellman-Ford. Instead of relaxing all edges in every iteration, SPFA only processes vertices whose distances were recently updated, since only their neighbors could potentially be relaxed.

How It Works

SPFA's average-case performance is significantly better than standard Bellman-Ford, often approaching O(E) on sparse graphs. However, its worst-case complexity is still O(V * E), the same as Bellman-Ford. SPFA is popular in competitive programming but appears less often in interviews than the standard algorithm.

To detect negative cycles with SPFA, track how many times each vertex is enqueued. If any vertex is enqueued V or more times, a negative cycle exists.

Time Complexity

The time complexity is O(V * E). The algorithm runs V-1 relaxation passes, and each pass relaxes all E edges, which gives (V-1) * E = O(V * E). The extra pass that checks for negative cycles adds one more O(E) scan, so it does not change the bound.

The early-exit optimization, which stops as soon as a pass makes no update, speeds the algorithm up in practice, but the worst case stays O(V * E). SPFA has the same O(V * E) worst case even though it often runs faster on sparse graphs.

Space Complexity

The space complexity is O(V) for the distance array, plus an optional predecessor array of the same size when you need to reconstruct the actual path. The edge list itself takes O(E).