Graph Algorithms8 min read

Bellman-Ford & SPFA

Handle negative weights and catch negative cycles
Bellman-Ford:\(O(VE)\)SPFA average:\(O(kE)\)negative cycle:Detected if dist updates after V−1 rounds

Imagine a price board at a currency exchange. Each row shows the current cost to get from one city to another. Every morning you check: "Can any route go cheaper if I re-route through a different city?" You keep updating the board until no more improvements are possible.

That's Bellman-Ford. Unlike Dijkstra, it doesn't assume all prices are positive — it handles negative edge weights and can even detect the pathological case where prices spiral to negative infinity (a negative cycle).

The Algorithm: V−1 Rounds of Relaxation

Initialize: dist[source] = 0, all other distances = ∞. Then repeat V−1 times:

For every edge (u, v, w) in the graph, check: if dist[u] + w < dist[v], update dist[v] = dist[u] + w.

Why V−1 rounds? Any simple path in a V-vertex graph has at most V−1 edges. Each round of relaxation can "activate" one more edge of the shortest path. After V−1 rounds, all simple shortest paths are fully computed — as long as no negative cycle exists.

Detecting Negative Cycles

After the V−1 rounds, run one more round. If any distance still decreases, a negative cycle is reachable from the source. Why? In a graph without negative cycles, shortest paths are simple paths — V−1 rounds already found them. Any further improvement means the algorithm is looping around a negative cycle, shaving off cost with each lap.

Negative cycles make shortest paths undefined: you can make the total cost arbitrarily negative by going around the cycle more times. Bellman-Ford is the standard algorithm to detect this condition.

SPFA (Shortest Path Faster Algorithm)

Bellman-Ford wastes time in each round relaxing edges from vertices whose distances haven't changed. SPFA fixes this with a queue: only enqueue vertices whose distances were just improved, and only relax their outgoing edges.

In practice, SPFA runs in \(O(kE)\) where k ≈ 2 on typical graphs — much faster than Bellman-Ford's \(O(VE)\). But adversarial inputs can make it degenerate back to \(O(VE)\), so for competitive programming it's treated with caution. For negative cycle detection, SPFA tracks how many times each vertex is enqueued — if any vertex is enqueued V times, a negative cycle exists.

Classic Application: Currency Arbitrage

Represent currencies as vertices, exchange rates as directed edges with weight −log(rate). A negative cycle in this graph means multiplying the exchange rates around the cycle gives a product greater than 1 — a profitable arbitrage loop. Bellman-Ford detects exactly this.

Click chart to zoom
Bellman-Ford: V−1 relaxation rounds followed by a negative-cycle check
Note: Dijkstra finalizes each vertex and never revisits it. Bellman-Ford relaxes every edge V−1 times — slow, but correct even with negative weights. Think of Bellman-Ford as the safe, thorough auditor vs. Dijkstra's fast, optimistic GPS.

Bellman-Ford with Negative Cycle Detection

def bellman_ford(n, edges, src):
    """
    n: number of vertices
    edges: list of (u, v, weight)
    Returns (dist, has_negative_cycle)
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0


    # V-1 relaxation rounds
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # early exit if stable


    # V-th round: check for negative cycle
    has_neg_cycle = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_neg_cycle = True
            break


    return dist, has_neg_cycle


# Graph: 0->1 (weight 6), 0->2 (7), 1->3 (-4), 2->1 (8), 3->0 (2)
edges = [(0,1,6),(0,2,7),(1,3,-4),(2,1,8),(3,0,2)]
dist, cycle = bellman_ford(4, edges, 0)
print(dist)   # [0, 2, 7, -2]
print(cycle)  # False


# Negative cycle example
edges2 = [(0,1,1),(1,2,-3),(2,0,1)]
_, cycle2 = bellman_ford(3, edges2, 0)
print(cycle2)  # True
Output
[0, 2, 7, -2]
False
True

Complexity

🐢 Bellman-Ford
V−1 rounds × E edges per round; fine for moderate-sized graphs
Polynomial but slow \(O(VE)\)
⚡ SPFA (average case)
Queue-based; only relaxes recently updated vertices — but worst case remains \(O(VE)\)
Much faster in practice \(O(kE)\), k ≈ 2
🔍 Negative cycle detection
Any improvement in round V means a reachable negative cycle exists
One extra round after V−1 \(O(E)\)
📊 vs Dijkstra
Use Dijkstra when all weights are non-negative; Bellman-Ford otherwise
Slower, but handles negative weights \(O(VE)\) vs \(O((V+E)\) log V)

Quick check

Why does Bellman-Ford run exactly V−1 relaxation rounds?

Continue reading