---
title: "0-1 BFS, Dial, Potentials, Johnson"
summary: What to run when the weights are small, zero-one, or negative — with the invariant that makes each one correct.
difficulty: hard
tags: [shortest-path, deque, potentials]
see: [shortest/dijkstra, shortest/bellman-ford]
---

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
:::note title="The invariant"
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)$.

```cpp zero-one-bfs.cpp
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);
    }
}
```

:::props title="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 `set` makes it $O(n + m)$ overall.
:::

## Small integer weights: Dial's algorithm
Bucket by distance: an array of $nC + 1$ vectors, where $C = \max_e w(e)$, plus a cursor walking forward. Each insertion is $O(1)$, total $O(nC + m)$.
Use it when $C \le 100$ or so; for larger $C$ but monotone keys, a **radix heap** gives $O((n + m)\log C)$ with tiny constants and no comparator.

```cpp dial.cpp
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
:::theorem title="Re-weighting (Johnson)"
Let $p: V \to \mathbb{R}$ be any function and define $w'(uv) = w(uv) + p(u) - p(v)$. Then for every path $P$ from $s$ to $t$,
$$\operatorname{len}_{w'}(P) = \operatorname{len}_{w}(P) + p(s) - p(t).$$
So all $s \to 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) = \operatorname{dist}(v_0, v)$ for a super-source $v_0$.
:::

:::proof
Sum $\sum_{uv \in P} (w(uv) + p(u) - p(v))$ — the $p$-terms telescope, leaving $p(s) - p(t)$. For non-negativity: $w'(uv) \ge 0 \iff p(v) \le p(u) + w(uv)$, which is exactly the triangle inequality satisfied by any distance vector. ∎
:::

```cpp johnson.cpp
// 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]; };
```

:::props title="Cost and payoff"
- all-pairs with negative weights: **$O(nm + n^2 \log n)$** instead of Floyd's $O(n^3)$ — 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 @flow/mcmf 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 (@shortest/bellman-ford).
:::

:::warning title="Potentials change distances, not orderings"
Forgetting to *undo* the shift when reporting $d$ is the classic bug: the printed distance is $\operatorname{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.
:::

:::problems
- [[CF 1242B]] 0-1 MST | https://codeforces.com/problemset/problem/1242/B | core | BFS on the complement instead of the graph
- [[CSES 1196]] Flight Routes | https://cses.fi/problemset/task/1196 | hard | $k$ shortest paths (Dijkstra with a per-vertex counter)
- [[CSES 2121]] Parcel Delivery | https://cses.fi/problemset/task/2121 | hard | min-cost max-flow, potentials inside
:::