vault

Bellman-Ford

11 min read

Bellman-Ford

Bellman-Ford computes single-source shortest paths in graphs that may contain negative edge weights, in O(V·E) time. It also detects negative cycles (a cycle whose total weight is negative — which makes “shortest path” ill-defined because you can loop the cycle infinitely). It’s slower than Dijkstra’s Algorithm but is the canonical answer when negative weights exist (e.g., currency arbitrage, certain DP-as-graph reductions).

1. Intuition — “Relax Every Edge, V-1 Times”

Bellman-Ford has the simplest core idea of any shortest-path algorithm:

  • Initialize dist[source] = 0, all other distances = ∞.
  • Repeat V-1 times: go through every edge (u, v, w) and try to “relax” it: if dist[u] + w < dist[v], update dist[v].
  • After V-1 rounds, all shortest distances are final.

That’s it. No heap, no priority, no greedy commitment. Just brute-force edge relaxation, repeated V-1 times.

Why V-1? Any shortest path in a graph with V vertices uses at most V-1 edges (it can’t visit any vertex twice without forming a cycle, and skipping the cycle would give a shorter path — unless the cycle is negative, which we’ll address). So after V-1 passes of “relax every edge,” every shortest path is fully discovered, regardless of edge ordering.

2. Tiny Worked Example

Graph (directed, with one negative edge):

    A → B  (weight 4)
    A → C  (weight 5)
    B → C  (weight -3)
    B → D  (weight 6)
    C → D  (weight 2)

Find shortest paths from A:

Initial: dist = {A: 0, B: ∞, C: ∞, D: ∞}

Iteration 1 — relax every edge:

  • A→B: dist[B] = min(∞, 0 + 4) = 4
  • A→C: dist[C] = min(∞, 0 + 5) = 5
  • B→C: dist[C] = min(5, 4 + (-3)) = 1 ← negative edge improves C!
  • B→D: dist[D] = min(∞, 4 + 6) = 10
  • C→D: dist[D] = min(10, 1 + 2) = 3 ← but this depends on iteration order

After iteration 1: dist = {A: 0, B: 4, C: 1, D: 3} (in this order; if we’d processed C→D before B→C, D would still be 10 after iteration 1, then improve in iteration 2).

Iteration 2 — relax every edge again:

  • All edges: no improvements.

We could have stopped here — but we continue 3 more iterations (V-1 = 4 - 1 = 3) to be safe. (Optimization: detect “no improvement this round” and break early.)

Final: dist[A] = 0, dist[B] = 4, dist[C] = 1, dist[D] = 3.

3. Pseudocode

bellman_ford(graph, source):
    dist := map vertex → ∞
    dist[source] := 0
    for i := 1 to V - 1:
        any_change := false
        for each edge (u, v, w) in edges:
            if dist[u] + w < dist[v]:
                dist[v] := dist[u] + w
                any_change := true
        if not any_change:
            break                              # early termination
    # negative cycle check:
    for each edge (u, v, w) in edges:
        if dist[u] + w < dist[v]:
            report "negative cycle reachable from source"
    return dist

4. Python Implementation

def bellman_ford(num_vertices, edges, source):
    """edges: list of (u, v, w) triples. Returns dist or None if negative cycle."""
    dist = {v: float('inf') for v in range(num_vertices)}
    dist[source] = 0
    for _ in range(num_vertices - 1):
        any_change = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                any_change = True
        if not any_change:
            break
    # detect negative cycle reachable from source
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None                        # negative cycle exists
    return dist

The early-termination optimization (any_change flag) makes Bellman-Ford much faster on inputs that don’t actually need all V-1 rounds — common in practice.

5. Detecting Negative Cycles

The “extra iteration” is the key trick. After V-1 rounds, all shortest paths up to V-1 edges are settled. If a V-th round still finds an improvement, that improvement uses a path with more than V-1 edges — which means the path repeats a vertex — which means there’s a cycle on the path that decreases total weight — which is a negative cycle.

Important nuance: Bellman-Ford detects negative cycles reachable from the source. If a negative cycle exists in some disconnected portion of the graph, Bellman-Ford from source won’t see it. To find any negative cycle in a graph, run Bellman-Ford from a virtual source connected to every vertex (this is the trick used in Johnson’s Algorithm).

To identify which vertices are affected by a negative cycle (their shortest distance is -∞), continue relaxation for one more pass and mark every vertex that gets improved — these are reachable from the cycle and thus have ill-defined distances.

6. Complexity

VariantTimeSpace
StandardO(V · E)O(V)
With early terminationO(V · E) worst, often much lessO(V)
SPFA (queue-based heuristic)O(V · E) worst, O(E) empirical avgO(V)

For sparse graphs (E = O(V)), this is O(V²). For dense (E = O(V²)), it’s O(V³).

This is much slower than Dijkstra’s Algorithm’s O((V+E) log V). The trade-off you accept for handling negative weights is roughly a factor of V / log V.

7. Comparison with Dijkstra

PropertyDijkstraBellman-Ford
Negative weights?❌ silent wrong answer✅ handles correctly
Negative cycle detection?N/A✅
Time complexityO((V+E) log V)O(V·E)
Greedy or DP?GreedyDP (relaxation = state update)
Distributed-friendly?No (needs global priority queue)Yes (each vertex relaxes locally)
Used in routing protocols?OSPF (link-state)RIP (distance-vector)

Pick Bellman-Ford only if (a) you have negative weights, (b) you need to detect negative cycles, or (c) you’re implementing a distributed protocol where vertices can only see local information.

8. SPFA — Shortest Path Faster Algorithm

A practical optimization of Bellman-Ford. Maintain a queue of vertices whose distance has been updated; only relax outgoing edges of queued vertices. Worst case is still O(V·E), but average case on many graphs is much better.

from collections import deque
 
def spfa(graph, source):
    """graph: dict node -> list of (neighbor, weight)."""
    dist = {source: 0}
    in_queue = {source}
    q = deque([source])
    count = {source: 1}                       # times each vertex enqueued
    while q:
        u = q.popleft()
        in_queue.discard(u)
        for v, w in graph[u]:
            nd = dist[u] + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                if v not in in_queue:
                    q.append(v); in_queue.add(v)
                    count[v] = count.get(v, 0) + 1
                    if count[v] > len(graph):
                        return None            # negative cycle
    return dist

SPFA's reputation

SPFA was once thought to be O(kE) average for some constant k, but adversarial inputs construct O(V·E) worst cases. In competitive programming, SPFA is sometimes banned from contests because well-crafted test cases can defeat it. Use plain Bellman-Ford if reliability matters; SPFA if you trust the input distribution.

9. Common Use Cases

9.1 Currency Arbitrage Detection

Currencies form a graph; exchange rates form edge weights. To detect arbitrage (a cycle of trades that produces profit), use weight = -log(rate) so multiplicative gain becomes additive cost. A negative cycle in the resulting graph corresponds to an arbitrage opportunity. Bellman-Ford finds it.

import math
def detect_arbitrage(rates):
    """rates[i][j] = exchange rate from currency i to j. Returns True if arbitrage exists."""
    n = len(rates)
    edges = [(i, j, -math.log(rates[i][j])) for i in range(n) for j in range(n) if i != j]
    return bellman_ford(n, edges, 0) is None

This is a real interview question at trading-firm and crypto-exchange shops.

9.2 Routing Information Protocol (RIP)

Each router maintains a distance vector to every destination. Periodically, it shares its vector with neighbors, who run a relaxation step. This is essentially distributed Bellman-Ford. RIP suffers from the “count-to-infinity” problem when links fail — a known weakness of distance-vector protocols.

9.3 Single-Source on Graphs with Constrained Negative Edges

Graphs where most edges are positive but some are negative (e.g., subsidies, bonuses, refunds) — Bellman-Ford is the safe default.

9.4 Within Other Algorithms

  • Johnson’s Algorithm: Bellman-Ford computes vertex potentials, allowing reweighting so that Dijkstra can then run on every vertex.
  • DP problems framed as shortest path with limited edges: e.g., “cheapest flight within K stops” can be solved as Bellman-Ford with K iterations (not V-1).
def cheapest_within_k_stops(n, flights, src, dst, k):
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):                    # k stops = k+1 edges
        new_dist = dist[:]
        for u, v, w in flights:
            if dist[u] != INF and dist[u] + w < new_dist[v]:
                new_dist[v] = dist[u] + w
        dist = new_dist
    return dist[dst] if dist[dst] != INF else -1

The new_dist = dist[:] copy is critical: without it, you’d allow chaining updates within a single iteration, breaking the “exactly i edges” semantics.

10. Common Interview Problems

ProblemPattern
LC 787 — Cheapest Flights Within K StopsBellman-Ford with K rounds
LC 1928 — Minimum Cost to Reach Destination in TimeModified shortest path (state = node + time)
Currency arbitrage / cycle profitNegative-cycle detection
LC 743 — Network Delay TimeEither Dijkstra (no negative weights) or Bellman-Ford
Interview classic: “shortest path with at most K edges”Bellman-Ford limited to K iterations

11. Pitfalls

11.1 Confusing Negative Edges with Negative Cycles

A graph can have negative edges but no negative cycle — Bellman-Ford handles this correctly. Negative cycles are different: they make shortest paths ill-defined (you can loop indefinitely). Always think about which case you’re in.

11.2 Detecting Cycles That Aren’t Reachable

Bellman-Ford from s only sees vertices reachable from s. A negative cycle in a disconnected portion is invisible. To detect any negative cycle, run from a virtual source connected to all vertices.

11.3 Forgetting Early Termination

Without the any_change early-exit flag, Bellman-Ford does the full V-1 iterations even when settled in 2. Trivial to add; massive practical speedup.

11.4 Mutating dist During Iteration

Be careful when implementing the “limited K-edges” variant — within one iteration, update new_dist from dist (not in-place). Otherwise distances cascade within the round and you compute “shortest path in up to K edges from this iteration’s start” rather than “exactly K relaxation rounds.”

11.5 Integer Overflow

dist[u] + w may overflow if dist[u] = INT_MAX. Either use float('inf') (Python — no overflow) or guard with if dist[u] != INF.

11.6 Iterating Over Edges Without an Edge List

Bellman-Ford fundamentally iterates over edges, not vertices. If your graph is given as an adjacency list, you need to either flatten to an edge list or iterate for u in vertices: for (v, w) in graph[u]. Either is fine; just don’t accidentally iterate vertices alone and miss the inner loop.

11.7 SPFA Worst-Case Trap

SPFA’s average-case speed is appealing, but adversarial inputs can degrade it to O(V·E). Don’t claim SPFA is “faster than Bellman-Ford” without qualifying.

12. Diagram — Relaxation Rounds

flowchart TD
  R0[Round 0<br/>dist source=0, others=∞] --> R1
  R1[Round 1<br/>relax every edge<br/>capture all 1-edge paths] --> R2
  R2[Round 2<br/>relax every edge<br/>now also 2-edge paths] --> R3
  R3[Round 3<br/>relax every edge<br/>now 3-edge paths] --> Rn[...]
  Rn --> RV[Round V-1<br/>all shortest paths captured]
  RV --> CHECK[Round V<br/>any improvement = negative cycle]

What this diagram shows. After round k, dist[v] is the shortest-path length using at most k edges. Since any shortest path uses at most V-1 edges, V-1 rounds suffice. A V-th round that still improves a distance reveals a negative cycle (a path > V-1 edges that beats the V-1-edge bound must repeat vertices and decrease cost — i.e., contain a negative cycle).

13. Why Bellman-Ford Is “DP, Not Greedy”

Bellman-Ford fits the tabulation DP template:

  • State: dist[v] = shortest distance to v using at most k edges (where k is the round number).
  • Recurrence: dist_k[v] = min(dist_{k-1}[v], min over edge (u, v, w): dist_{k-1}[u] + w).
  • Order: rounds 1, 2, …, V-1.

Dijkstra, by contrast, is greedy: it commits to the minimum unsettled vertex at each step. Bellman-Ford makes no such commitment — it just relaxes every edge in every round. This is why Bellman-Ford handles negative weights (no premature commitment) but pays the V·E cost (no priority-driven shortcut).

14. Open Questions

  • Yen’s improvement (early termination per vertex, edge ordering by SCC) — is it ever taught at interview level? Generally no; competitive programming yes.
  • When is SPFA reliably faster than plain Bellman-Ford in practice? For random sparse graphs, often 5-10× faster; for adversarial / regular structures, no improvement.

15. See Also

Graph View

Backlinks