Dijkstra earns its speed from a greedy bet that one negative edge voids. Bellman-Ford makes no bet at all. It relaxes every edge in the graph, over and over, V - 1 times, letting correct distances spread one edge further with each round. No heap, no ordering, no assumptions about edge signs, and a price tag of O(VE) for the generality.

The same loop hides a second feature: run one round beyond V - 1, and any distance that still improves proves the graph contains a negative cycle, a loop whose total weight is below zero. For problems like currency arbitrage, that alarm is the entire point.

Why is V - 1 enough? A shortest path never revisits a node, so it uses at most V - 1 edges, and each full sweep guarantees the correct distances reach at least one edge further along every such path. Watch the propagation on the classic 5-node example with edges 0→1(6), 0→2(7), 1→4(-4), 2→3(-3), 3→1(-2), and a few others. Round 1 lands d = [0, 6, 7, 4, 2], with node 3 already improved through the -3 edge. Predict round 2: which distance does the 3→1 edge now improve?

Node 1 drops from 6 to 4 - 2 = 2, and that improvement is only visible because round 1 fixed node 3 first. Round 3 cashes the chain one edge further: node 4 falls to 2 - 4 = -2 through the now-cheap node 1. Round 4 changes nothing, and the early exit fires. Distances a Dijkstra would have sworn final in the wrong order simply settle, one ripple of correctness per round.

def bellman_ford(n: int, edges: list[tuple[int, int, int]], start: int) -> list[float] | None:
    # edges hold (source, target, weight); returns None on a negative cycle
    INF = float("inf")
    distance = [INF] * n
    distance[start] = 0

    # The longest simple path has n - 1 edges, so n - 1 rounds settle everything
    for _ in range(n - 1):
        updated = False
        for source, target, weight in edges:
            # Only relax from nodes that have been reached
            if distance[source] != INF and distance[source] + weight < distance[target]:
                distance[target] = distance[source] + weight
                updated = True

        # Early exit: a quiet round means a settled graph
        if not updated:
            break

    # Round n: any improvement now proves a negative cycle
    for source, target, weight in edges:
        if distance[source] != INF and distance[source] + weight < distance[target]:
            return None

    return distance

After V - 1 rounds, every shortest simple path has been fully propagated, so a V-th round should find nothing to do. If it improves anything, the improving path must use V edges, and V edges across V nodes forces a repeated node: a cycle, and one that lowered the total, meaning its weight is negative. Walking it again lowers the total again, forever, so "shortest path" stops being a meaningful question for anything that can reach the loop.

You might think that makes negative cycles a degenerate case nobody wants. The famous application inverts the framing: model currencies as nodes and exchange rates as edge weights (negated logarithms, so multiplying rates becomes adding weights), and a negative cycle is a sequence of trades that ends with more money than it started with. Bellman-Ford's alarm is an arbitrage detector.

The round structure solves a problem the faster algorithms can't touch. Cheapest Flights Within K Stops asks for the cheapest route using at most K + 1 edges, and Dijkstra's finalization ignores budgets entirely: the cheapest way to a city may use too many stops while a pricier, shorter route is the only legal one. Bellman-Ford's rounds are already denominated in edges, so running exactly K + 1 rounds answers the question, with one adjustment.

Each round must read from a snapshot of the previous round's distances instead of the live array. Updating in place lets a single round chain several edges (relax A→B, then immediately B→C using the fresh value), which quietly busts the budget. The copy enforces the meaning "round r = best cost using at most r edges", and that one detail is the entire solution.

Three flags in a problem statement point here. Negative weights anywhere, since no amount of care rescues the greedy alternatives. Cycle detection as the actual deliverable, arbitrage being the canonical dress it arrives in. And hop or stop budgets, where the round-counting variant turns a constraint other algorithms fight into the loop counter itself.

In the broader family, this is the generalist's tool: slower than Dijkstra on friendly inputs, simpler than anything else on hostile ones, and the conceptual parent of the distributed routing protocols that ran the early internet, where each router relaxes its own edges and correctness still spreads one hop per exchange.

Simple loop, sharp edges. Five to respect:

Two checks first: why do V - 1 rounds suffice for any negative-cycle-free graph, and what does an improvement in round V prove? The budgeted variant is the star of the set: