Bellman-Ford Algorithm

Bellman-Ford computes single-source shortest paths by repeatedly relaxing every edge in the graph — if going through edge (u,v) with weight w gives a shorter path to v than the best known so far, update it — and it works even with negative edge weights because it never commits to a vertex's distance being final until it has given every edge enough chances to correct it; after at most V−1 rounds of relaxing all E edges, every shortest path (which visits at most V−1 edges, since a shortest path never repeats a vertex) has been discovered.

Recognize the pattern

• You need shortest paths from one source and the graph may contain negative edge weights (e.g. currency arbitrage, cost that can be a refund/credit, differential constraints).
• You need to detect whether a negative-weight cycle exists (and is reachable from the source) — Dijkstra cannot do this at all, it just produces wrong answers silently.
• The graph is small-to-medium and dense-ish, or E is not much larger than V, so an O(V·E) pass is acceptable.
• You are building Johnson's algorithm (all-pairs shortest paths with negative edges) — Bellman-Ford is the reweighting step.
• You see constraints like "difference constraints" / "x − y ≤ c" systems — these reduce directly to a Bellman-Ford shortest-path graph.

Baseline: brute force vs. Bellman-Ford

Naive baseline — enumerate all simple paths from the source to each vertex and take the minimum weight one. A simple path has at most V−1 edges, but the number of simple paths is exponential in V (up to (V−1)! in a dense graph), so this is O(V!) in the worst case — completely infeasible beyond tiny graphs.

Bellman-Ford's insight: instead of enumerating paths, track only the best known distance to each vertex, dist[v], and repeatedly ask "can any single edge improve any dist[v] right now?" A shortest path (if one exists, i.e. no negative cycle on it) has at most V−1 edges, so after V−1 full sweeps over all E edges, dist[v] is guaranteed correct for every v — because sweep k is guaranteed to correctly fix the shortest path to any vertex whose optimal path uses exactly k edges, by induction on the number of edges in the optimal path.

Complexity, derived

Time: the main loop runs V−1 times (outer loop), and each iteration relaxes every one of the E edges once (inner loop) doing O(1) work per edge (one comparison, maybe one update) → (V−1)·E = O(V·E). The negative-cycle check is one extra full sweep of E edges → O(E), which does not change the asymptotic total.

Space: O(V) for the dist[] array and O(V) for an optional predecessor[] array used to reconstruct paths. The edge list itself is input, O(E), not extra working space beyond what's needed to iterate it.

Contrast with Dijkstra: Dijkstra's binary-heap implementation is O((V+E) log V) because it only ever "visits" each vertex once and each edge once, using the heap to always pick the cheapest frontier vertex next — that greedy shortcut is exactly what breaks under negative edges, and exactly why Bellman-Ford must brute-force V−1 full sweeps instead.

Traced worked example

Graph (this is the standard CLRS teaching example), source s. Edges in relaxation order (t,x),(t,y),(t,z),(x,t),(y,x),(y,z),(z,x),(z,s),(s,t),(s,y):

Distances after each full pass (V=5, so 4 passes needed):

Key steps, edge by edge within pass 2 (dist entering pass 2: s=0, t=6, x=∞, y=7, z=∞): (t,x) relaxes first — 6+5=11 < ∞, so x becomes 11. (t,y): 6+8=14, not better than 7, skip. (t,z): 6−4=2 < ∞, so z becomes 2. (x,t): x=11, 11−2=9, not better than 6, skip. (y,x): now compares against x's current value of 11, not ∞ — 7−3=4 < 11, so x improves again to 4 within the same pass. (y,z): 7+9=16, not better than 2, skip. The rest don't improve anything this pass, giving the row-2 snapshot (t=6, x=4, y=7, z=2) shown above. This is the core lesson: relaxations within a single pass can chain — a vertex relaxed earlier in the pass (x via t) can be immediately relaxed again later in the same pass (x via y), so you must always compare against the latest dist[], not the value from the start of the pass. Pass 3 relaxes x→t (4−2=2 < 6), improving t after x had already improved — showing a vertex's distance can still get better even after it looked "settled" in an earlier pass. Pass 4 relaxes t→z again (2−4=−2 < 2). A 5th verification pass changes nothing, so there is no negative-weight cycle and the final distances (t=2, x=4, y=7, z=−2) are correct.

Reference implementation (Java)

import java.util.*;

class BellmanFord {
    static final int INF = Integer.MAX_VALUE / 2; // avoid overflow on add

    static class Edge {
        int from, to, weight;
        Edge(int from, int to, int weight) {
            this.from = from; this.to = to; this.weight = weight;
        }
    }

    // Returns dist[] from source, or null if a negative-weight cycle
    // reachable from source is detected.
    static int[] shortestPaths(int V, List<Edge> edges, int source) {
        int[] dist = new int[V];
        Arrays.fill(dist, INF);
        dist[source] = 0;

        // Relax all edges V-1 times.
        for (int i = 0; i < V - 1; i++) {
            boolean changed = false;
            for (Edge e : edges) {
                if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[e.from] + e.weight;
                    changed = true;
                }
            }
            if (!changed) break; // early exit: converged before V-1 rounds
        }

        // One more pass: if anything still relaxes, a negative cycle
        // is reachable from the source.
        for (Edge e : edges) {
            if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
                return null; // negative-weight cycle detected
            }
        }
        return dist;
    }
}

Pitfalls

• Negative cycle reachable from source: shortest path is undefined (−∞) for every vertex reachable through the cycle. Concretely, if you kept relaxing past V−1 passes, each additional lap around the cycle would keep shaving more off dist[] for every vertex downstream of it, forever — there is no finite shortest-path value to converge to. That is precisely why the extra verification pass exists: if it still finds an improving edge after V−1 guaranteed-sufficient passes, the only possible explanation is such a cycle, so the algorithm reports "undefined" instead of a wrong finite number. Never just report the V−1-pass result as final without that check.
• Overflow when relaxing from INF: if dist[u] is a sentinel like Integer.MAX_VALUE and you add a weight to it without guarding, you overflow into a bogus small/negative number and spuriously "relax" unreachable vertices. Always check dist[u] != INF (or use a half-max sentinel) before adding.
• Confusing "no more relaxations" with "no negative cycle" too early — you must run the full V−1 passes (or until convergence) before the cycle-check pass; checking after fewer passes can falsely report a cycle when the graph simply hadn't converged yet.
• Edge order doesn't matter for correctness, only for how many passes are needed in practice — V−1 is a guaranteed worst-case bound regardless of order, but a lucky order may converge in far fewer passes (use the early-exit optimization above), and relaxations can chain within one pass (see the traced example).
• Cycle not reachable from source but present elsewhere in the graph won't be caught by a single-source run — Bellman-Ford only certifies paths reachable from the chosen source.

When to use / when not — trade-off vs. Dijkstra

Use Bellman-Ford when the graph can have negative weights, when you must certify "no negative cycle", or as the reweighting subroutine in Johnson's all-pairs algorithm. Use Dijkstra whenever all weights are non-negative and performance matters — it is asymptotically faster and is the default choice for road networks, routing, and most practical shortest-path problems. As a middle ground, SPFA (a queue-driven relaxation order) is often faster than plain Bellman-Ford in practice on sparse graphs, but its worst case is still O(V·E) and it is not asymptotically better — don't rely on it for adversarial inputs.

Takeaways

• Bellman-Ford relaxes every edge V−1 times because a shortest simple path has at most V−1 edges — that bound, not cleverness about ordering, is what guarantees correctness.
• Within a single pass, an earlier relaxation can immediately feed a later one (a vertex can improve twice in the same pass) — always relax against the current dist[], not a snapshot from the start of the pass.
• It trades Dijkstra's O((V+E) log V) speed for the ability to handle negative edges and to certify the absence of a negative-weight cycle with one extra pass.
• If a negative-weight cycle is reachable from the source, distances through it are undefined (−∞) — they would keep shrinking forever with more passes — which is exactly what the extra verification pass detects.
• Always guard arithmetic against the INF sentinel, and always run the confirmation pass — reporting distances without checking for a negative cycle is a silent correctness bug.
• It is the workhorse inside Johnson's algorithm, which reweights a graph with Bellman-Ford so that Dijkstra can then be run safely from every vertex for all-pairs shortest paths.

Recall question

Why does relaxing all E edges exactly V−1 times guarantee correct shortest-path distances from the source, assuming no negative-weight cycle is reachable from it — and why does a single additional relaxation pass finding an improvement prove such a cycle exists?

Authored for this guide; concepts and the worked example follow the standard treatment in Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS), "The Bellman-Ford Algorithm" chapter on single-source shortest paths.