---
title: "Bellman–Ford and Negative Weights"
summary: n−1 rounds of relaxation, why that is enough, and the two extra lines that output the negative cycle.
difficulty: core
tags: [shortest-path, negative, cycles]
time: n m
space: n
prereq: [shortest/dijkstra]
see: [directed/cycles, shortest/sparse-tricks]
---

Bellman–Ford is the only shortest-path algorithm that survives negative edges, because it never *settles* anything: it simply applies every relaxation $n-1$ times and trusts the count.

:::theorem title="Correctness"
After $k$ rounds of "relax every edge once", $d[v] \le$ the length of the shortest walk from $s$ to $v$ using at most $k$ edges. Hence after $n-1$ rounds, if no negative cycle is reachable, $d[v] = \operatorname{dist}(s,v)$.
:::

:::proof
Induction on $k$. Round $k$ processes edge $uv$ where $u$ is reachable in $\le k-1$ edges, giving $d[v] \le d^{(k-1)}[u] + w \le$ (best $(k-1)$-walk to $u$) $+ w$. Conversely every $\le k$-edge walk ends in some edge $uv$ whose prefix is a $\le (k-1)$-edge walk, so the DP is exhaustive. A shortest *walk* with no negative cycle can be taken simple, hence has $\le n-1$ edges (cycle removal, @foundations/walks) — which is exactly the value that makes $n-1$ rounds sufficient. ∎
:::

```cpp bellman-ford.cpp
struct Edge { int u, v; ll w; };
vector<ll> d(n, INF);
d[s] = 0;
for (int it = 0; it < n - 1; it++)
    for (const auto& e : edges)
        if (d[e.u] < INF && d[e.u] + e.w < d[e.v])
            d[e.v] = d[e.u] + e.w, par[e.v] = e.u;

// one extra round: an improvement means a reachable negative cycle
int x = -1;
for (const auto& e : edges)
    if (d[e.u] < INF && d[e.u] + e.w < d[e.v]) { x = e.v; par[x] = e.u; break; }
if (x != -1) {                       // walk back n times to land inside the cycle
    for (int i = 0; i < n; i++) x = par[x];
    vector<int> cyc{x};
    for (int y = par[x]; y != x; y = par[y]) cyc.push_back(y);
    cyc.push_back(x);
    reverse(cyc.begin(), cyc.end());
    cout << "NO\n";                  // or print cyc
    return;
}
```

:::note title="The `for (i = 0; i < n; i++) x = par[x]` trick"
$x$ is a vertex whose distance still improves, so its parent chain must pass through the negative cycle. Following `par` $n$ times from any vertex of a graph with a cycle of length $\le n$ lands *on* the cycle — after that, walking parents until you return to $x$ enumerates exactly the cycle. 8 lines instead of a separate DFS.
:::

## SPFA: the queue version, and why to distrust it
```cpp spfa.cpp
queue<int> q; vector<char> inq(n);
d[s] = 0; q.push(s); inq[s] = 1;
while (!q.empty()) {
    int u = q.front(); q.pop(); inq[u] = 0;
    for (auto [v, w] : g[u]) if (d[u] + w < d[v]) {
        d[v] = d[u] + w;
        if (!inq[v]) { inq[v] = 1; q.push(v); }
    }
}
// negative cycle detected by: cnt[v] = cnt[u] + 1 > n-1  (or "v enqueued > n times")
```
SPFA is Bellman–Ford with a worklist: only vertices whose value changed are scanned. It is $O(nm)$ in the worst case and usually linear-ish in practice — which means **someone can construct a test that kills it** (grid graphs with back-edges and negative edges are the classic anti-SPFA generator). Use it when negative weights are guaranteed and $nm$ fits; otherwise re-weight (@shortest/sparse-tricks, Johnson) and run Dijkstra.

:::props title="What Bellman–Ford is genuinely the best answer to"
- **negative weights** with $n \le 500$, $m \le 10^4$ — $5 \times 10^6$ relaxations, no thinking,
- **detect/print a negative cycle** (the parent trick above),
- **"cheapest route with at most k edges"** — run exactly $k$ rounds, and the answer is $d^{(k)}[t]$: a whole family of problems ("flight with at most $k$ stops", CSES-style) is *just* this truncated Bellman–Ford,
- **difference constraints**: $x_v - x_u \le c$ for edges $u \to v$ with weight $c$ — feasible $\iff$ no negative cycle, and the distances are a solution,
- **arbitrage / currency exchange**: maximise $\prod$ rates ⟹ minimise $\sum \log(1/r)$ ⟹ negative cycle.
:::

:::example title="At most k edges, in 6 lines"
```cpp
for (int step = 0; step < k; step++) {
    auto nd = d;                                  // note: snapshot, not in-place!
    for (const auto& e : edges) nd[e.v] = min(nd[e.v], d[e.u] + e.w);
    d = nd;
}
```
Copying `d` is what makes the round count exact. Updating in place mixes "up to $k$ edges" with "up to $k+1$" and silently accepts more edges than allowed — the single most common Bellman–Ford bug in contest code.
:::

:::problems
- [[CSES 1197]] Cycle Finding | https://cses.fi/problemset/task/1197 | core | negative cycle output
- [[CSES 1680]] Longest Flight Route | https://cses.fi/problemset/task/1680 | core | "at most k edges" DP
- [[CSES 1672]] Shortest Routes II | https://cses.fi/problemset/task/1672 | easy | contrast with Floyd
:::