Bellman-Ford Theory

Definition

Given a weighted directed graph G=(V,E) that may contain negative edge weights (but no negative cycles reachable from the source), Bellman-Ford computes the shortest path distances from a source vertex s to every other vertex. It uses at most |V|−1 passes to propagate shortest path improvements progressively along edges.

Key Concepts

• Relaxation: Attempt to improve dist[v] via edge (u,v): if dist[u] + w < dist[v] then update.
• Pass: One full iteration over all edges; after k passes shortest paths using ≤ k edges are found.
• Negative Cycle Detection: A further improvement after |V|−1 passes implies a cycle of overall negative weight.
• Early Exit: If no edge relaxes in a pass, algorithm can terminate early.
• Edge List Friendly: Works directly from edge list without adjacency priority logic.

Algorithm Steps

1. Initialize dist[source]=0; others = ∞; parent[v]=NIL.
2. Repeat |V|−1 times: for each edge (u,v,w) perform relaxation.
3. If in a pass no relaxation occurs, break early.
4. Run final pass: if any edge can still relax -> negative cycle detected.
5. Reconstruct path by following parent pointers.

Optimizations

• Early Stop: Track if any relaxation occurred in a pass.
• Queue-Based Variant (SPFA): Only process vertices that had improved distances (not worst-case safe, can degrade).
• Cycle Tracking: On detection mark vertices reachable from a relaxing chain for cycle reporting.
• Edge Bucketing: Group edges by from-vertex for slight locality gain.

Time & Space Complexity

K = number of passes until convergence (K ≤ V−1). Better for sparse graphs or when shortest paths use few edges.

Pseudocode

1BellmanFord(G, w, source):
2  for each vertex v in G.V:
3    dist[v] ← ∞
4    parent[v] ← NIL
5  dist[source] ← 0
6  // |V|-1 relaxation passes
7  for i from 1 to |V|-1:
8    updated ← false
9    for each edge (u, v) in G.E:
10      if dist[u] + w(u,v) < dist[v]:
11        dist[v] ← dist[u] + w(u,v)
12        parent[v] ← u
13        updated ← true
14    if not updated:      // early stop optimization
15      break
16  // Negative cycle detection
17  for each edge (u, v) in G.E:
18    if dist[u] + w(u,v) < dist[v]:
19      return "NEGATIVE CYCLE" // or mark cycle vertices
20  return dist, parent

Applications

• Shortest paths with negative weights (no negative cycles)
• Negative cycle detection (arbitrage, fraud loops)
• Preprocessing for Johnson's all-pairs algorithm
• Distance constraints analysis in scheduling
• Evaluating feasibility in difference constraints systems

Comparison with Dijkstra

Edge Cases & Pitfalls

• Negative Cycle: Distances undefined; mark nodes or report cycle path.
• Large Edge Count: O(V·E) becomes prohibitive for dense graphs; consider reweight + Dijkstra.
• Floating Precision: Repeated additions can accumulate error; use tolerance for comparisons.
• SPFA Worst Case: Queue-based optimization can degrade to O(V·E).