Chapter 6 · Shortest Paths
Bellman–Ford and Negative Weights
n−1 rounds of relaxation, why that is enough, and the two extra lines that output the negative cycle.
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.
After k rounds of "relax every edge once", d[v] ≤ 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] = dist(s,v).
Induction on k. Round k processes edge uv where u is reachable in ≤ k-1 edges, giving d[v] ≤ d(k-1)[u] + w ≤ (best (k-1)-walk to u) + w. Conversely every ≤ k-edge walk ends in some edge uv whose prefix is a ≤ (k-1)-edge walk, so the DP is exhaustive. A shortest walk with no negative cycle can be taken simple, hence has ≤ n-1 edges (cycle removal, Walks, Trails, Paths, Cycles) — which is exactly the value that makes n-1 rounds sufficient. ∎
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;
}for (i = 0; i < n; i++) x = par[x] trickx 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 ≤ 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
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 (0-1 BFS, Dial, Potentials, Johnson, Johnson) and run Dijkstra.
What Bellman–Ford is genuinely the best answer to
- negative weights with n ≤ 500, m ≤ 104 — 5 × 106 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: xv - xu ≤ c for edges u → v with weight c — feasible ⇔ no negative cycle, and the distances are a solution,
- arbitrage / currency exchange: maximise ∏ rates ⟹ minimise ∑ log(1/r) ⟹ negative cycle.
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.