Chapter 6 · Shortest Paths
0-1 BFS, Dial, Potentials, Johnson
What to run when the weights are small, zero-one, or negative — with the invariant that makes each one correct.
Dijkstra's heap is an oracle for "extract minimum". Whenever the distances you generate are almost sorted, a cheaper container suffices — and each special case below is exactly that observation.
#Weights in {0, 1}: 0-1 BFS
While the deque is non-empty, the distances it stores take at most two consecutive values, and the container is sorted non-decreasing from front to back.
Push a weight-0 relaxation to the front, a weight-1 relaxation to the back: the front insertion keeps the two-valued order, so popping always yields a currently-minimal vertex — a Dijkstra where extract-min costs O(1). Total O(n + m).
deque<int> dq;
d.assign(n, INF); d[s] = 0; dq.push_back(s);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto [v, w] : g[u]) if (d[u] + w < d[v]) {
d[v] = d[u] + w;
if (w == 0) dq.push_front(v); else dq.push_back(v);
}
}Where weights 0/1 come from in disguise
- "buy a ticket / walk for free along existing tracks": add 1 to a new edge, 0 to an existing one,
- grid problems where a straight step costs 0 and a turn costs 1 (run BFS on directed states (cell, direction)),
- "minimum number of changes" formulations: keep = 0, change = 1,
- the complement-graph BFS (CSES/CF 1242B style): edges of weight 1 in the complement = non-edges of G, and iterating unvisited vertices with a
setmakes it O(n + m) overall.
#Small integer weights: Dial's algorithm
Bucket by distance: an array of nC + 1 vectors, where C = maxe w(e), plus a cursor walking forward. Each insertion is O(1), total O(nC + m). Use it when C ≤ 100 or so; for larger C but monotone keys, a radix heap gives O((n + m)log C) with tiny constants and no comparator.
int C = max_w, K = n * C + 2;
vector<vector<int>> bucket(K);
vector<int> d(n, INF); int cur = 0;
d[s] = 0; bucket[0].push_back(s);
for (int seen = 0; seen < n; ) {
while (cur < K && bucket[cur].empty()) cur++;
if (cur >= K) break;
int u = bucket[cur].back(); bucket[cur].pop_back();
if (d[u] != cur) continue; // stale
seen++;
for (auto [v, w] : g[u]) if (d[u] + w < d[v]) {
d[v] = d[u] + w; bucket[d[v]].push_back(v);
}
}#Negative weights without Bellman–Ford: potentials
Let p: V → ℝ be any function and define w'(uv) = w(uv) + p(u) - p(v). Then for every path P from s to t,
So all s → t paths keep their relative order: shortest paths are unchanged, and w' is non-negative whenever p is a feasible potential, e.g. p(v) = dist(v0, v) for a super-source v0.
Sum ∑uv ∈ P (w(uv) + p(u) - p(v)) — the p-terms telescope, leaving p(s) - p(t). For non-negativity: w'(uv) ≥ 0 ⇔ p(v) ≤ p(u) + w(uv), which is exactly the triangle inequality satisfied by any distance vector. ∎
// 1) super-source with 0-weight edges to everyone; 2) Bellman-Ford for p
// 3) re-weight every edge; 4) Dijkstra from each source; 5) undo with d[u] - p(s) + p(t)
vector<ll> p(n, 0);
for (int it = 0; it < n; it++) // n rounds: one extra to catch negative cycles
for (auto [u, v, w] : edges) if (p[u] + w < p[v]) p[v] = max(-1e15, p[u] + w);
auto wt = [&](int u, int v, ll w) { return w + p[u] - p[v]; };Cost and payoff
- all-pairs with negative weights: O(nm + n2 log n) instead of Floyd's O(n3) — the same bound as n Dijkstras, but valid with negatives,
- A\* / min-cost flow: reduced costs
w + pot[u] - pot[v]are exactly this re-weighting; keeping them non-negative is what lets Min-Cost Max-Flow use Dijkstra instead of Bellman–Ford in every augmentation, - LP duality: a feasible potential is a dual solution; "no negative cycle" is feasibility of the difference-constraint system (Bellman–Ford and Negative Weights).
Forgetting to undo the shift when reporting d is the classic bug: the printed distance is dist(s,t) + p(s) - p(t). Also, p must come from a full Bellman–Ford run over the whole graph (super-source included) — a partial one can leave a negative reduced cost and then Dijkstra is simply wrong.