Bellman-Ford

What this chapter covers

Dijkstra's algorithm had one hard requirement: no negative edge weights. Bellman-Ford is what you reach for when that requirement can't be met — when some edges make things cheaper, as in a graph of currency exchanges, a scheduling problem with rebates, or any system where a move can refund cost. Dijkstra breaks on negatives because it settles each node the first time it's reached, trusting that nothing cheaper can arrive later, and a negative edge violates exactly that trust. Bellman-Ford abandons the clever settle-once order and does something almost embarrassingly simple instead: relax every edge in the graph, then do it again, and again, V−1 times. It's slower — O(V·E) — but it copes with negative weights, and with one extra pass it detects a negative cycle, the situation where "shortest path" stops meaning anything because you could loop forever getting cheaper. This chapter builds it, watches distances ripple outward pass by pass, and measures how often Dijkstra quietly returns a wrong answer once negative edges appear.

A bit of history

The algorithm carries the names of Richard Bellman, who published it in 1958, and Lester Ford Jr., who described it in 1956, with Edward Moore also arriving at it independently in 1959 — so it's sometimes called Bellman-Ford-Moore. Bellman was the same figure who coined "dynamic programming" a few years earlier, and Bellman-Ford is really dynamic programming on graphs: the shortest distance to a node using at most $k$ edges is built from the shortest distances using at most $k-1$ edges, and each pass advances $k$ by one. That framing — the answer for $k$ edges depends on the answer for $k-1$ — is why the algorithm feels so different from Dijkstra's greedy settling and why it lands in the same intellectual family as the dynamic-programming chapters later in this book. Its most enduring practical use was distance-vector routing: the original ARPANET routing protocol and later RIP had each router repeatedly share its distance estimates with neighbors and relax — a distributed Bellman-Ford running across an entire network.

The intuition

Forget cleverness about which node to process next. Bellman-Ford considers all edges equally and just relaxes every one of them: for each edge $u \to v$ of weight $w$, if reaching $v$ through $u$ is cheaper than $v$'s current estimate, lower it. Do that for the whole edge list, and you've completed one pass. The guarantee after one pass is modest but precise: every node whose shortest path uses just one edge now has its final distance. After two passes, every node reachable in at most two edges is final. After $k$ passes, everything reachable in at most $k$ edges. Since a shortest path in a graph with no negative cycle visits at most $V-1$ edges (more than that would repeat a node, and repeating a node on a shortest path only helps if the loop is negative), $V-1$ passes settle everything.

The correctness doesn't depend on the sign of the weights at all — relaxation only ever lowers an estimate toward the truth, and after enough passes every shortest path has had its edges relaxed in order. That's why negatives are fine where they wrecked Dijkstra: Bellman-Ford never freezes a node, so a cheaper route discovered on a later pass is always still welcome. And it hands you cycle detection for free. After $V-1$ passes everything should be final, so if a $V$-th pass can still relax some edge, there must be a negative cycle feeding it — a loop whose total weight is negative, around which distances fall without bound. Then "shortest path" is undefined, and the honest answer is to report the cycle rather than a number.

Complexity: how it scales

Each pass relaxes all $E$ edges in $O(E)$, and there are $V-1$ passes, so Bellman-Ford is $O(V \cdot E)$ — on a dense graph that's $O(V^3)$, markedly slower than Dijkstra's $O((V+E)\log V)$. Space is $O(V)$. A common optimization stops early if a pass changes nothing (the distances have converged), which the implementation does, but the worst case stands. You pay that extra factor of $V$ for one thing: correctness in the presence of negative weights. The face-off measures exactly what you're buying — how often the faster algorithm, Dijkstra, returns a wrong distance as negative edges become more common:

With no negative edges the two agree perfectly — Dijkstra is correct and you should use it. But as negatives appear, Dijkstra's settle-once shortcut starts returning wrong distances: at 30% negative edges it got about 5% of node distances wrong, silently, with no error or warning. Bellman-Ford was correct on every one. That's the trade in a sentence: Dijkstra is faster but only valid on non-negative graphs, and on negative ones it doesn't fail loudly — it just lies. Bellman-Ford is the slower algorithm that tells the truth, and detects the one case (a negative cycle) where there is no truth to tell.

What it's good at, what it isn't

Bellman-Ford is the right tool whenever edge weights can be negative and you still need shortest paths — currency arbitrage detection, systems of difference constraints (each "x − y ≤ c" is an edge), distance-vector routing where it runs distributed across a network, and any problem you can encode with negative-cost moves. Its cycle-detection ability is often the real reason to use it: reporting "there is no shortest path, here is a negative cycle" is frequently more valuable than a distance, because in arbitrage or constraint-solving the cycle is the answer. It's also simple to implement and reason about, being just repeated relaxation with no priority queue.

Where it loses is speed on non-negative graphs, where its factor-of-$V$ overhead is pure waste — use Dijkstra there. It's single-source, like Dijkstra; for all-pairs shortest paths with negatives you'd use Floyd-Warshall (next chapter) or Johnson's algorithm. And on very large graphs the $O(VE)$ cost can be prohibitive, which is why real routing systems layer optimizations on top (the SPFA queue-based variant, early termination) or avoid negative weights by construction.

The data, or the inputs

The face-off runs on random directed acyclic graphs — a DAG can never contain a cycle, so never a negative one, which lets us make a large fraction of edges negative while keeping the shortest-path problem well-defined. For each, it compares Dijkstra's distances against Bellman-Ford's and counts how many nodes Dijkstra gets wrong. Correctness is cross-checked two independent ways: against Dijkstra on non-negative graphs (where both are right), and against Floyd-Warshall (next chapter's all-pairs method, which owes nothing to Bellman-Ford's approach) on negative-edge graphs — plus hundreds of graphs with a planted negative cycle to confirm detection. The animation runs Bellman-Ford on a small graph with one negative edge (drawn red), the numbers in the nodes being their current distance estimates.

Build it, one function at a time

The whole algorithm — relax every edge V−1 times, then one pass to detect a negative cycle:

def bellman_ford(n, edges, start):
    """Shortest-path distances from `start`, edges given as (u, v, w) with any sign.
    Relax all E edges, V-1 times: after pass k, every node reachable by a shortest path of
    <= k edges has its final distance, and a shortest path has at most V-1 edges. Returns
    (dist, parent, has_negative_cycle). If a Vth relaxation still improves something, a
    negative cycle is reachable and the distances below it are meaningless."""
    dist = [float("inf")] * n
    parent = [-1] * n
    dist[start] = 0
    for _ in range(n - 1):                      # V-1 passes
        changed = False
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w            # relaxation — the same primitive as Dijkstra
                parent[v] = u
                changed = True
        if not changed:
            break                                # converged early: no pass changed anything
    # one more pass: any further improvement proves a reachable negative cycle
    has_neg_cycle = any(
        dist[u] != float("inf") and dist[u] + w < dist[v] for u, v, w in edges
    )
    return dist, parent, has_neg_cycle

Reconstructing the path, with the two failure modes made explicit:

def shortest_path(n, edges, start, target):
    """Rebuild the cheapest path start → target from the parent pointers. Returns
    (path, cost), or (None, inf) if unreachable, or (None, -inf) if a negative cycle makes
    the distance unbounded below."""
    dist, parent, neg = bellman_ford(n, edges, start)
    if neg:
        return None, float("-inf")
    if dist[target] == float("inf"):
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1], dist[target]

Watch it work

Here's Bellman-Ford on a five-node graph, from node 0. The number inside each node is its current distance estimate — ∞ until the ripple reaches it — and the red edge (2→1, weight −3) is the negative one that makes this graph a trap for Dijkstra. Watch the passes: in pass 1 the estimates spread out in edge-list order, and node 1 first gets distance 4 from the direct edge 0→1; but then the negative edge 2→1 relaxes it down to 2, and in pass 2 that improvement ripples onward to nodes 3 and 4. Dijkstra would have settled node 1 at 4 and never revisited it. Bellman-Ford, relaxing everything every pass, catches the cheaper route and propagates it — and a final pass with no change confirms the distances are final:

The complete code

The from-scratch tab is Bellman-Ford with cycle detection and path reconstruction; the library tab is the settle-once Dijkstra it's raced against — the fast algorithm that gets the wrong answer here — with the networkx call you'd use in production noted at the top. Flip between them.

"""Bellman-Ford — shortest paths from a source when edges may have NEGATIVE weights,
the case Dijkstra can't handle. Negative edges are not exotic: a graph of currency
trades, a game where some moves refund cost, a scheduling problem with rebates — anywhere
"traversing this edge makes things cheaper" is meaningful.

Dijkstra fails on negatives because it settles a node the first time the heap pops it,
trusting that no cheaper route can arrive later — which a negative edge can violate.
Bellman-Ford gives up that clever settle-once order entirely. It just relaxes EVERY edge,
V-1 times over. Each full pass guarantees every shortest path of one more edge is found,
and since a shortest path visits at most V-1 edges, V-1 passes suffice. It's slower —
O(V·E) instead of O((V+E) log V) — but it copes with negatives, and one extra pass detects
a negative cycle, where "shortest path" stops meaning anything (you could loop forever
getting cheaper).
"""


# region: bellman_ford
def bellman_ford(n, edges, start):
    """Shortest-path distances from `start`, edges given as (u, v, w) with any sign.
    Relax all E edges, V-1 times: after pass k, every node reachable by a shortest path of
    <= k edges has its final distance, and a shortest path has at most V-1 edges. Returns
    (dist, parent, has_negative_cycle). If a Vth relaxation still improves something, a
    negative cycle is reachable and the distances below it are meaningless."""
    dist = [float("inf")] * n
    parent = [-1] * n
    dist[start] = 0
    for _ in range(n - 1):                      # V-1 passes
        changed = False
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w            # relaxation — the same primitive as Dijkstra
                parent[v] = u
                changed = True
        if not changed:
            break                                # converged early: no pass changed anything
    # one more pass: any further improvement proves a reachable negative cycle
    has_neg_cycle = any(
        dist[u] != float("inf") and dist[u] + w < dist[v] for u, v, w in edges
    )
    return dist, parent, has_neg_cycle
# endregion


# region: shortest_path
def shortest_path(n, edges, start, target):
    """Rebuild the cheapest path start → target from the parent pointers. Returns
    (path, cost), or (None, inf) if unreachable, or (None, -inf) if a negative cycle makes
    the distance unbounded below."""
    dist, parent, neg = bellman_ford(n, edges, start)
    if neg:
        return None, float("-inf")
    if dist[target] == float("inf"):
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1], dist[target]
# endregion

"""The library counterpart and the contrast. In production you'd call
networkx.single_source_bellman_ford, which is the same algorithm with negative-cycle
detection built in:

    import networkx as nx
    G = nx.DiGraph()
    for u, v, w in edges:
        G.add_edge(u, v, weight=w)
    length, path = nx.single_source_bellman_ford(G, source)   # raises on a negative cycle

But the more instructive comparison is against DIJKSTRA — the faster algorithm that gets
the wrong answer here. `dijkstra` below is the heap version from the previous chapter; the
trace generator runs it on graphs with negative edges to show exactly where and by how
much it goes wrong, which is the whole reason Bellman-Ford exists.
"""
import heapq


# region: dijkstra
def dijkstra(n, edges, start):
    """Dijkstra's defining optimization made explicit: SETTLE each node the first time it's
    popped and never revisit it. That's exactly what makes it fast (each node processed once)
    and exactly what makes it WRONG on negative edges — once a node is settled its distance is
    frozen, so a cheaper route discovered later is silently ignored. Valid only for
    non-negative weights; here it's the cautionary contrast to Bellman-Ford."""
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [float("inf")] * n
    dist[start] = 0
    settled = [False] * n
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if settled[u]:
            continue
        settled[u] = True                    # frozen from here on — the source of the error
        for v, w in adj[u]:
            if not settled[v] and d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (d + w, v))
    return dist
# endregion

Scratch vs library

The instructive comparison isn't our Bellman-Ford against a library's, but Bellman-Ford against Dijkstra — two shortest-path algorithms where the faster one is silently wrong on the inputs the slower one is built for. That's a different failure mode from most of this book's face-offs. Usually the wrong tool is slower or uses more memory; here Dijkstra is faster and returns a plausible-looking answer that is simply incorrect, with no crash and no warning. The lesson is about preconditions: an algorithm's guarantee is only as good as its assumptions, and Dijkstra's assumption — non-negative weights — is easy to violate without noticing. Knowing why Dijkstra needs non-negativity (it settles nodes once) tells you exactly when you must step down to Bellman-Ford and pay the factor of $V$. In production you'd use networkx's bellman_ford or single_source_bellman_ford; building it yourself is what makes "Dijkstra gave the wrong distance" a predictable consequence instead of a baffling bug.

Where you'll actually meet it

Bellman-Ford's headline application is network routing: distance-vector protocols — the original ARPANET algorithm, RIP, and the path-vector BGP that stitches the internet together — are distributed Bellman-Ford, each router relaxing distance estimates shared by its neighbors. It detects arbitrage in foreign-exchange and cryptocurrency markets, where a negative cycle in the log-rate graph is a risk-free profit loop. It solves systems of difference constraints in schedulers and compilers (each constraint is an edge, feasibility is the absence of a negative cycle). It underlies Johnson's all-pairs algorithm, which uses one Bellman-Ford pass to reweight a graph so Dijkstra can safely run from every node. And it's the standard classroom answer to "shortest paths with negative edges," because its logic is transparent. Wherever negatives appear or a negative cycle must be found, Bellman-Ford is the tool.

Takeaways

Bellman-Ford finds shortest paths from a source even with negative edge weights by relaxing every edge $V-1$ times — dynamic programming on graphs, where pass $k$ settles every distance reachable in $k$ edges — in $O(V \cdot E)$. It never settles a node, so it tolerates the negative edges that break Dijkstra's settle-once shortcut, and a $V$-th pass detects the negative cycles where shortest paths cease to exist. It's the slower, truthful counterpart to Dijkstra: use Dijkstra when weights are non-negative, step down to Bellman-Ford when they aren't.

Both algorithms so far compute distances from a single source. The next chapter asks for all of them at once — the shortest distance between every pair of nodes — and answers it with Floyd-Warshall, a strikingly short triple loop that is dynamic programming of a different flavor, handles negative edges like Bellman-Ford, and computes the entire distance matrix in $O(V^3)$.