Bellman-Ford, Round Counts, and Negative-Cycle Detection

The round-based shortest-path method is the one that survives when weights may be negative, and its structure is almost aggressively simple: sweep every edge, repeat, stop after a fixed number of sweeps. The fixed number is the interesting part, because it is simultaneously the correctness argument, the termination guarantee, and the hook on which negative-cycle detection hangs.

Why the bound is |V| - 1

Consider the state after round $k$, where a round relaxes every edge in the graph once, in any fixed order. Claim: after round $k$, for every vertex $v$, the label $d[v]$ is at most the weight of the cheapest path from $s$ to $v$ that uses at most $k$ edges.

The proof is an induction on $k$ with an inner induction on the position of the edge within the round. Let $p$ be a cheapest path of at most $k$ edges to $v$, and let $u$ be its last-but-one vertex. By hypothesis, after round $k-1$, $d[u]$ already equals the weight of a cheapest path of at most $k-1$ edges to $u$. During round $k$, the edge $(u,v)$ is relaxed at some point; at that moment $d[u]$ holds a value no larger than its end-of-round-$k-1$ value, because labels never increase. So the relaxation sets $d[v]$ to at most $w(p)$. The inner induction is what makes the “at some point” argument work: even if $(u,v)$ is relaxed before other edges of round $k$, the value it reads is already final from the previous round.

Since a shortest path in a graph with no reachable negative cycle can always be taken simple, it contains at most $|V| - 1$ edges. Hence $|V| - 1$ rounds suffice, and the labels equal the true distances. If the graph has $|V|$ vertices and the source is one of them, that is $|V| - 1$ rounds and $O(|V| \cdot |E|)$ relaxation calls; for a graph with a million vertices and five million edges, on the order of $5 \times 10^{12}$ calls, which is why the method is not used on large graphs unless the weights force it.

The order of edges within a round does not affect correctness, but it affects how fast convergence happens in practice: a round that happens to process edges in path order settles everything in one pass. The bound is the worst case over orders, not a typical case.

The extra pass

After $|V| - 1$ rounds, run one more round. If any edge can still be relaxed, the labels are not a fixed point, and by the argument in Relaxation and the Optimality Condition a fixed point would have been correct. So the failure to reach one means the hypothesis “no reachable negative cycle” is false.

The converse direction needs care. If a reachable negative cycle exists, does the extra pass always detect it? Yes, and the argument is local to the cycle. Suppose the extra pass found nothing relaxable, so that every edge $(u,v)$ with $d[u]$ finite satisfies $d[v] \le d[u] + w(u,v)$. Adding that inequality around a cycle $C$ telescopes the labels away and leaves $0 \le w(C)$, so no reachable cycle is negative. Contrapositively, a reachable negative cycle must leave at least one of its own edges relaxable after $|V|-1$ rounds, and the extra pass finds it. The check is therefore exact in both directions, not merely a heuristic.

Implementation detail that bites: the check must compare against labels after the final round, and the graph must be the one actually searched. Running the check on a graph where the source cannot reach the cycle produces no detection, correctly, because a negative cycle in a disconnected component does not affect distances from $s$.

From rounds to a work queue

Relaxing all $|E|$ edges in a round is wasteful when only a handful of labels changed. The label-correcting variant keeps a queue of vertices whose label changed, pops one, and relaxes only its outgoing edges, enqueueing any vertex whose label improved. This is Bellman-Ford with a schedule chosen adaptively, so it inherits the correctness argument and the negative-cycle condition, but its worst case is unchanged; an adversarial graph can force each vertex into the queue $O(|V|)$ times, giving the same $O(|V||E|)$ bound.

from collections import deque

def shortest_paths(n, edges, source):
    """edges: list of (u, v, w). Returns (dist, parent, has_negative_cycle)."""
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    INF = float('inf')
    dist = [INF] * n
    parent = [-1] * n
    dist[source] = 0
    in_queue = [False] * n
    depth = [0] * n              # edges on the path that produced the current label
    q = deque([source])
    in_queue[source] = True
    while q:
        u = q.popleft()
        in_queue[u] = False
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                depth[v] = depth[u] + 1
                if depth[v] >= n:        # a simple path needs at most n-1 edges
                    return dist, parent, True
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True
    return dist, parent, False

The depth test is a detection shortcut rather than a proof of optimality: depth[v] counts the edges on the path that produced the current label, and a chain of $|V|$ edges must repeat a vertex. The repeated segment is a cycle of the predecessor graph, and it is negative, because the labels along the chain strictly decreased. So the test cannot fire falsely, and it fires before the queue would otherwise diverge. The cost is one counter per vertex.

Two scheduling refinements are worth knowing by name because they appear in real code. A first-in-first-out queue gives the behaviour above. A last-in-first-out structure, a stack, tends to follow a single path deeply before backtracking, which is often much faster on road-like graphs and much worse on graphs built to defeat it. Ordering the queue by current label, a closest-first rule, recovers something close to Dijkstra’s behaviour when weights are nonnegative.

Extracting the cycle, not just its existence

Detection yields a vertex $x$ whose label improved on the extra pass. That vertex need not lie on the cycle; it is reachable from one. To find the cycle itself, walk predecessor pointers from $x$ exactly $|V|$ times. Since there are only $|V|$ vertices, some vertex $y$ must repeat; the segment of the walk between the two occurrences of $y$ is a closed walk. It is a cycle in the graph-theoretic sense only after removing any repeated interior vertices, but its total weight is negative, because the walk descended strictly in label at every step.

The walk is well defined only if predecessor pointers are consistent. In a queue-based implementation where pointers are overwritten during relaxation, the pointer chain can be transiently cyclic or can point into a part of the graph that has since been improved; walking it $|V|$ steps is still safe because the walk is bounded, but the extracted walk may not be the minimal negative cycle. Reporting the weight is reliable; reporting a minimal cycle is a separate, harder problem.

What the method cannot do

Three limitations are structural rather than incidental.

It is $O(|V||E|)$, and no schedule fixes that in the worst case; the improvement available is in constants and in typical-case behaviour, not in the bound. The size at which it becomes unusable is set by the product $|V| \cdot |E|$, not by the per-edge constant.

It computes distances from one source. Running it $|V|$ times gives $O(|V|^2|E|)$, which is worse than the dedicated all-pairs methods compared in Floyd-Warshall, Johnson Reweighting, and the All-Pairs Choice.

It requires the whole graph to be known before the first round. Streaming or dynamic variants exist, but they are not the same algorithm and do not carry the same guarantee; an edge inserted after the last round invalidates the fixed point, and re-running from scratch is the only simple correct response.

Where the round count reappears

The $|V|-1$ bound is not specific to this algorithm. It is the statement that shortest paths are simple, and it shows up wherever a path is built incrementally: in the layered-graph construction used for resource-constrained routing, in the dynamic program over path length that underlies the minimum-mean-cycle computation discussed in Minimum Mean Cycle and the Shape of Negative-Weight Answers, and in the verification step of any implementation that claims to have converged. When a piece of code iterates “until no change, at most n times”, the n is usually this bound wearing a different hat.