Bellman-Ford Algorithm

Description

Negative edge weights come up naturally: refunds, energy regained going downhill, or exchange rates turned into costs with a logarithm. They break Dijkstra's rule that the closest node is final. They also allow a cycle whose total weight is negative, around which a "shortest" path could loop forever. Bellman-Ford relaxes every edge, round after round, until distances stop changing. It handles negative weights, reports a reachable negative cycle, and can cap the number of edges a path may use.

We'll go from simple to more technical:

1. The pattern: V - 1 rounds of relaxing every edge, then one more to check for cycles.
2. A second flavor: capping the number of edges (cheapest flight with at most k stops).
3. Where it runs in production (distance-vector routing, arbitrage checks).
4. What breaks it: stopping early, relaxing in place, and unreachable cycles.

The approach

int[] bellmanFord(int n, int[][] edges, int src) {               // edges: {u, v, w}
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int round = 1; round <= n - 1; round++) {                 // V - 1 rounds
        boolean changed = false;
        for (int[] e : edges) {
            if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
                dist[e[1]] = dist[e[0]] + e[2];
                changed = true;
            }
        }
        if (!changed) break;                                       // a quiet round: everything is final
    }
    for (int[] e : edges) {                                        // one extra round
        if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
            return new int[]{Integer.MIN_VALUE};                   // still improving: negative cycle
        }
    }
    return dist;
}

def bellman_ford(n: int, edges: list[list[int]], src: int) -> list[float] | None:   # edges: [u, v, w]
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(n - 1):                               # V - 1 rounds
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:                    # inf + w is still inf: no guard needed
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                                        # a quiet round: everything is final
    for u, v, w in edges:                                # one extra round
        if dist[u] + w < dist[v]:
            return None                                  # still improving: negative cycle
    return dist

Relaxing an edge means "if going through it is cheaper, take it". A shortest path that doesn't loop has at most V - 1 edges, and each round of relaxing every edge extends the correctly-computed prefix of that path by at least one more edge - whatever order the edges are listed in. So after V - 1 rounds every distance is right. If a further round still improves something, no finite shortest path exists: a negative cycle is being exploited. The != Integer.MAX_VALUE guard keeps unreachable nodes out of it (and avoids overflowing infinity). In Python, float("inf") makes the guard unnecessary: inf + w is still inf, which never beats anything.

A second flavor: capping the number of edges

"Cheapest flight with at most k stops" is Bellman-Ford stopped after k + 1 rounds - with one change. Relaxing in place lets a single round chain several new edges, so after round i distances may already use more than i edges. When the edge count matters, each round must read last round's values and write into a copy:

for (int round = 0; round <= k; round++) {          // k stops = at most k + 1 flights
    int[] next = cost.clone();                       // read from cost, write to next
    for (int[] f : flights) {
        if (cost[f[0]] != INF && cost[f[0]] + f[2] < next[f[1]]) next[f[1]] = cost[f[0]] + f[2];
    }
    cost = next;
}

for _ in range(k + 1):                   # k stops = at most k + 1 flights
    nxt = cost[:]                        # read from cost, write to a COPY (`nxt = cost` is the same list)
    for u, v, price in flights:
        if cost[u] + price < nxt[v]:
            nxt[v] = cost[u] + price
    cost = nxt

With flights 0->1 (100), 1->2 (100), 0->2 (500) and k = 0 (direct flights only), the answer is 500. In place, the round sets cost[1] = 100 and then immediately uses it for 1->2, reporting 200 - a two-flight route.

Where you'll see it

Distance-vector routing protocols (RIP) are distributed Bellman-Ford: each router repeatedly shares its distance table with neighbors and relaxes. Currency-arbitrage detection turns exchange rates into weights -log(rate), so a loop whose rates multiply to more than 1 becomes a negative cycle. Constraint systems of the form x_v - x_u <= w solve as shortest paths, with a negative cycle meaning "no solution".

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why are V - 1 rounds always enough when there's no negative cycle?

2. An extra round after V - 1 rounds still lowers a distance. What does that mean?

3. Flights 0->1 (100), 1->2 (100), 0->2 (500), at most 0 stops from 0 to 2. Why does in-place relaxation report 200?

Key takeaways

• Bellman-Ford relaxes every edge V - 1 times; that's enough because a shortest path has at most V - 1 edges.
• A round with no change means the distances are final - early exit is safe; a fixed smaller number of rounds is not.
• One extra round that still improves something proves a reachable negative cycle.
• For "at most k edges", relax from a copy of the previous round's distances.
• O(V * E): slower than Dijkstra, but it handles negative weights.