Bellman-Ford, in depth: the relaxation invariant, early exit, hop-limited paths, distance-vector routing and difference constraints

Relaxation, and why order matters

Every single-source shortest path algorithm keeps an estimate d[v] for each vertex, initialised to 0 at the source and infinity elsewhere. Relaxing an edge (u, v) with weight w means checking whether going through u improves v: if d[u] + w < d[v], set d[v] = d[u] + w and remember u as v's parent. Two facts make relaxation safe. Each estimate is always the length of some real path from the source, or infinity, so it can never fall below the true distance. And once d[u] equals the true distance and u comes just before v on a shortest path, relaxing (u, v) makes d[v] exact too.

Algorithms differ only in the order they relax edges. Dijkstra relaxes outgoing edges of vertices in order of final distance, which works only when no edge is negative. A topological order works for acyclic graphs, as in longest paths in a DAG. Bellman-Ford chooses no clever order at all and compensates by repetition.

The algorithm and why n - 1 passes suffice

If the graph has no negative cycle reachable from the source, every shortest path can be taken to be simple, so it has at most n - 1 edges. Call such a path s = v0, v1, ..., vk. After the first full pass over the edges, the edge (v0, v1) has been relaxed while d[v0] was exact, so d[v1] is exact. After the second pass, d[v2] is exact, whatever order the edges were in. By induction, after pass i every vertex whose shortest path has at most i edges is exact. So n - 1 passes suffice, and one more pass that still improves something proves a negative cycle is reachable.

def bellman_ford(n, edges, src):
    # edges: list of (u, v, w); vertices are 0..n-1
    INF = float("inf")
    dist = [INF] * n
    parent = [-1] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                changed = True
        if not changed:                 # early exit: a quiet pass means we are done
            break
    for u, v, w in edges:               # one more pass to detect a reachable negative cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("negative cycle reachable from source")
    return dist, parent

The running time is O(nm) for n vertices and m edges, against O((n + m) log n) for Dijkstra with a binary heap. The dist[u] != INF guard is not cosmetic: with integer sentinels such as 10**18, adding a negative weight to an unreachable vertex's sentinel makes it look reachable.

Worked example, traced

Use the graph above with source s and relax edges in the order (t,x), (t,y), (t,z), (x,t), (y,x), (y,z), (z,x), (z,s), (s,t), (s,y). That order is deliberately unhelpful: the edges leaving s come last.

Each pass fixes exactly one more edge of the longest shortest path, s, y, x, t, z, which is the induction argument made visible. Now reverse the luck: put (s,t) and (s,y) first, then (t,x), (t,y), (t,z), (y,x), (y,z), (x,t), (z,x), (z,s). The first pass already ends with t = 2, x = 4, y = 7 and z = 2, the second pass sets z = -2, and the third pass is quiet, so early exit stops after three main-loop passes instead of four, each followed by the one checking pass. Edge order changes the constant, never the answer.

Making it faster without losing the guarantee

Three practical improvements keep the guarantee while cutting real work.

• Early exit. Stop after a pass with no change, as in the code above. On graphs where shortest paths have few edges this turns n - 1 passes into a handful.
• Yen's ordering. Number the vertices arbitrarily and split the edges into those going from a lower to a higher number and those going the other way. In each pass, sweep vertices in increasing order relaxing the first set, then in decreasing order relaxing the second. Any shortest path is a sequence of increasing and decreasing runs, and each pass consumes one of each, which roughly halves the worst-case number of passes.
• Only relax what changed. If d[u] did not change since u's edges were last relaxed, relaxing them again cannot help. Tracking that with a queue gives SPFA. It is often much faster in practice but keeps the O(nm) worst case, and adversarial inputs reach it.

Shortest paths with at most K edges

A common interview and production problem is the cheapest route with at most K stops, for example flights where each stop has a cost or risk. That is a shortest path with at most K + 1 edges, and Bellman-Ford's induction gives it almost for free: after i passes, paths of up to i edges are exact. But that statement is a lower bound, not a limit. In the in-place version, a single pass can propagate along several edges if they happen to come in the right order, as the second trace above showed when t reached 2 through a three-edge path in pass one. To enforce the limit, every pass must read only the previous pass's distances.

def cheapest_within_k_stops(n, edges, src, dst, k):
    INF = float("inf")
    prev = [INF] * n
    prev[src] = 0
    for _ in range(k + 1):              # k stops means at most k + 1 edges
        cur = prev[:]                   # copy: relax FROM prev, write INTO cur
        for u, v, w in edges:
            if prev[u] != INF and prev[u] + w < cur[v]:
                cur[v] = prev[u] + w
        prev = cur
    return -1 if prev[dst] == INF else prev[dst]

The copy is the whole trick. Relaxing from cur instead of prev silently allows longer paths, and tests with friendly edge orders will pass. The cost is O(k m) time and O(n) extra memory. Negative cycles are harmless here because the edge budget bounds every walk.

Distance-vector routing

Bellman-Ford distributes naturally. Give every router a table of its best-known cost to each destination and let routers periodically send that table to their neighbours. A router that hears neighbour B advertise cost c to network N, over a link of cost w, relaxes: if c + w beats its own entry, it adopts B as next hop. That is distance-vector routing, and RIP is the classic protocol built on it. No router needs the whole map, and with stable links the tables converge to shortest paths.

The weakness is bad news. When A loses its link to N, it may hear B still advertising N at cost 2, unaware that B's route went through A. A adopts cost 3 through B, B updates to 4 through A, and the two count upward. RIP bounds the damage by defining 16 as unreachable, which also caps network diameter at 15 hops. Split horizon, where a router does not advertise a route back to the neighbour it learned it from, and poison reverse, where it advertises that route back as unreachable, fix the two-router loop; triggered updates speed convergence. Larger loops can still count to infinity, which is one reason link-state protocols such as OSPF, which run Dijkstra on a full map, dominate larger networks.

Difference constraints

A system of difference constraints is a set of inequalities of the form x_j - x_i <= w. They appear in scheduling (task j starts at least 3 units after task i ends), timing analysis and layout. Rewrite each constraint as x_j <= x_i + w, which is exactly the relaxation condition for an edge from i to j with weight w. Add a virtual source with a zero-weight edge to every variable and run Bellman-Ford. If there is a negative cycle, the constraints are infeasible: summing the inequalities around the cycle gives 0 <= a negative number. Otherwise the distances are a solution.

def solve_difference_constraints(n, constraints):
    # constraints: list of (j, i, w) meaning x_j - x_i <= w; variables 0..n-1
    src = n
    edges = [(i, j, w) for j, i, w in constraints] + [(src, v, 0) for v in range(n)]
    try:
        dist, _ = bellman_ford(n + 1, edges, src)
    except ValueError:
        return None                     # infeasible
    return dist[:n]

# x1-x2<=0, x1-x5<=-1, x2-x5<=1, x3-x1<=5, x4-x1<=4, x4-x3<=-1, x5-x3<=-3, x5-x4<=-3
cons = [(0,1,0), (0,4,-1), (1,4,1), (2,0,5), (3,0,4), (3,2,-1), (4,2,-3), (4,3,-3)]
print(solve_difference_constraints(5, cons))   # [-5, -3, 0, -1, -4]

Any solution can be shifted by a constant, so if you need non-negative start times, add the negated minimum to every value. The solution Bellman-Ford returns has a useful property: it maximises the sum of the variables subject to all of them being at most zero, which in scheduling means as late as possible relative to the virtual source.

Johnson&amp;#x27;s potentials and negative cycles

The same construction powers Johnson's algorithm for all-pairs shortest paths on sparse graphs with negative edges. One Bellman-Ford run from a virtual source gives a potential h(v) for every vertex, the reweighted edges w(u,v) + h(u) - h(v) are all non-negative, and n runs of Dijkstra finish the job in O(nm log n). For negative cycles themselves, the n-th pass test, extracting the cycle by walking parent pointers, and marking every vertex whose distance is minus infinity are treated in the negative-cycle article linked above.

Choosing an algorithm

Failure modes

• Overflow from sentinels. Adding to an infinity stand-in without the reachability guard creates false paths or wraps integers.
• In-place relaxation in hop-limited problems. Passes tests by luck and fails on other edge orders.
• Undirected graphs with negative edges. An undirected negative edge is a two-edge negative cycle, so shortest paths do not exist; model direction explicitly.
• Detecting only reachable cycles. A single-source run cannot see cycles the source cannot reach; use a virtual source when you need any cycle.
• Floating-point weights. Log-transformed rates, as in currency graphs, accumulate rounding error; require an improvement larger than a small epsilon before relaxing.

What to do next

1. Implement bellman_ford with early exit and run it on the worked graph with both edge orders; confirm four and three main-loop passes before the checking pass.
2. Write the K-stops version, then break it deliberately by relaxing from cur and find an edge order that exposes the bug.
3. Encode a small project schedule as difference constraints and check the start times by hand.
4. Compare against Dijkstra on a graph with non-negative weights and measure the speed gap as the graph grows.
5. Read the negative-cycle and SPFA pages linked above to finish the family.