Edmonds-Karp and Dinic's algorithm both belong to the same family: search the whole residual graph for a path from source to sink, push flow along it, repeat. Every intermediate state along the way is a genuine, conservation- respecting flow. Push-relabel (Goldberg-Tarjan) throws that family's whole strategy away. It never searches for a path at all — instead it lets flow overflow at individual nodes on purpose, then fixes each overflow with a strictly local decision: does this node have a neighbor it's allowed to send its extra flow to right now? If yes, push some. If no, raise this node's own height just enough to create one, and try again. No node ever needs to know what's happening three hops away.
Formally: every node other than the source S and sink T gets a height
h(v), all starting at 0 except h(S) = V (fixed) and h(T) = 0 (fixed,
and never changes). A node also has an excess — inflow minus outflow, normally required to be
zero everywhere but S and T for something to count as a real flow, but allowed to sit
positive here mid-algorithm; a state with positive excess elsewhere is called a preflow, not a
flow. A residual edge u→v is admissible only when h(u) = h(v) + 1 —
exactly one step downhill. Every active node (excess > 0, not S or T) repeats one
of two moves: push as much excess as the residual edge allows across any admissible edge it
has, or, if it has none, relabel — raise its own height to 1 + min over the
heights of every node it still has residual capacity toward, the smallest change that creates a new admissible
edge. The algorithm stops when no node but S/T has excess left. The demo below reuses
Edmonds-Karp's and Dinic's exact graph, so all three pages can be compared directly.
Two facts about heights, both easy to check locally, are what let push-relabel skip the "search the whole
graph" step Edmonds-Karp and Dinic's both depend on. First, heights only ever go up — a relabel is the only
thing that changes a node's height, and it always increases it. Second, the algorithm never lets the
invariant h(u) ≤ h(v) + 1 break for any residual edge u→v: a push only ever fires on
an edge where that already holds with equality, and it can only shrink or reverse that same edge's residual
capacity, never any other edge out of u; a relabel exists specifically to restore the invariant
for every residual edge out of the node being relabeled, all at once.
That invariant is the whole proof. Suppose, at any point, a path of residual edges existed from S
to T — length k, at most V − 1 since a simple path can't repeat a node.
Chaining the invariant across every edge on that path gives h(S) ≤ h(T) + k. But h(S) = V
and h(T) = 0 are both fixed for the algorithm's entire run, so this would require V ≤ k ≤
V − 1 — a contradiction. No such path can ever exist, at any point during execution, not just at the
end. So when the algorithm finally halts (no active vertex remains, the preflow has become a real flow), that
flow is already known to have no augmenting path in its residual graph — the exact condition Edmonds-Karp and
Dinic's each run one final BFS to confirm. Push-relabel gets that guarantee for free, baked into an invariant
it maintains at every single step, rather than checking for it once at the very end.
Same six nodes and eight directed edges as the Edmonds-Karp and Dinic's demos, labeled
flow/capacity. Press Step or Run. Every node shows two small
badges: a height (bottom-right, always visible — this is h(v)) and an excess (top-left, only
visible while positive — this is the "overflow" waiting to be pushed or relabeled away). The currently active
node is outlined; a push highlights the admissible edge it uses, a relabel just updates that node's height
badge. Preflow initialization saturates every edge leaving S before the main loop even starts —
watch A and B pick up excess immediately, before either has done anything itself.
Matches the demo above one for one — same generic "pick any active vertex" selection rule, same push/relabel
logic — just without the yield points the demo uses to show every individual operation:
function pushRelabel(numNodes, edges, s, t) {
const cap = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
edges.forEach(e => { cap[e.a][e.b] += e.cap; });
const flow = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
const h = new Array(numNodes).fill(0);
h[s] = numNodes;
const excess = new Array(numNodes).fill(0);
// Preflow init: saturate every edge leaving the source.
edges.forEach(e => {
if (e.a === s) {
flow[s][e.b] += e.cap;
flow[e.b][s] -= e.cap;
excess[e.b] += e.cap;
excess[s] -= e.cap;
}
});
function activeVertex() {
for (let v = 0; v < numNodes; v++) {
if (v !== s && v !== t && excess[v] > 0) return v;
}
return -1;
}
let u;
while ((u = activeVertex()) !== -1) {
let pushed = false;
for (let v = 0; v < numNodes; v++) {
const residual = cap[u][v] - flow[u][v];
if (residual > 0 && h[u] === h[v] + 1) {
const amount = Math.min(excess[u], residual);
flow[u][v] += amount;
flow[v][u] -= amount;
excess[u] -= amount;
excess[v] += amount;
pushed = true;
break; // one push per iteration, same granularity the demo shows
}
}
if (pushed) continue;
let minHeight = Infinity;
for (let v = 0; v < numNodes; v++) {
if (cap[u][v] - flow[u][v] > 0) minHeight = Math.min(minHeight, h[v]);
}
h[u] = minHeight + 1; // smallest raise that creates a new admissible edge
}
return excess[t]; // no active vertices left: preflow is now a maximum flow
}Dropping the height admissibility check doesn't slow the algorithm down — it breaks it outright,
immediately. A version that pushes an active node's excess across the first residual edge with any
spare capacity, ignoring h(u) = h(v) + 1 entirely, was run against this page's own demo graph: it
halts after just 4 pushes and 0 relabels at a max flow of 0,
not the true 15. What happens is exactly what the check exists to prevent: after the preflow
init pushes S→A and S→B (2 of those 4 pushes), both A and B
still have a residual edge straight back to S — the reverse of the edge that just gave them their
excess, and the first residual edge index order finds for each. Without the height rule to forbid it, each
node's very next move is to hand its entire excess right back where it came from (the other 2 pushes), and the
"algorithm" halts having moved nothing anywhere. The height invariant isn't an optimization; it's what forces
excess to flow generally downhill, toward the sink, instead of sloshing back uphill to the source the instant
it's offered the chance.
Relabeling to the maximum neighbor height instead of the minimum breaks correctness the
same way, just with two relabels in between instead of zero. Swapping h[u] = 1 + min(...)
for h[u] = 1 + max(...) — a plausible typo, since both read as "pick a neighbor height and add
one" — was also run against the demo graph: 4 pushes and 2 relabels, max
flow 0 again. A's residual neighbors after preflow init are S
(height 6, via the reverse edge), B, and C (both height 0); taking the max relabels
A straight to height 7 in one move — high enough to push its entire excess back to S
immediately, the same washback failure as above, just reached via one extra relabel instead of skipping the
check completely. B does the same thing right after. The minimum is what makes a relabel
the smallest possible change: it opens exactly one new admissible edge, toward the closest-to-T
neighbor available, rather than leaping straight to whichever neighbor happens to be closest to the source.
A preflow is not a flow, and reading intermediate state as if it were gives a wrong number.
Unlike Edmonds-Karp or Dinic's, where every step in the demo represents a real, conservation-respecting flow
you could stop and report, push-relabel's intermediate states genuinely violate conservation — after just the
first preflow-init step here, excess(A) = 10, meaning 10 more flow enters A than
leaves it, which is not a valid flow by definition. Summing "flow received at T so far" mid-run
(what the demo's stats bar shows) is meaningful as a running lower bound, but the algorithm's actual answer —
a value provably equal to the true max flow — only exists once every node but S and T
reaches zero excess. Stopping early and reporting excess(T) as "the answer" isn't a rounding
error, it's reporting a number that isn't the max flow, isn't a flow's value at all, and can be arbitrarily far
from 15 depending on when you stopped.
Time: O(V²E) for the generic algorithm — the version implemented above and in
the demo, which picks any active vertex with no particular rule. The bound comes from two pieces: relabels are
capped at O(V) per node (a node's height can rise to at most 2V − 1 before it's
provably able to route all its excess back toward the source) for O(V²) total, saturating pushes
(the residual edge empties completely) are capped at O(VE) since each one needs another relabel
before that same edge can be pushed again, and non-saturating pushes (excess runs out before the edge does) are
bounded by O(V²E) via a potential-function argument — the term that dominates the total. Smarter
active-vertex selection rules tighten this without changing the algorithm's actual operations: FIFO order (always
work the longest-waiting active vertex) gets O(V³); always picking the highest-labeled
active vertex gets O(V²√E), the standard textbook bound and the one usually meant by "push-relabel"
without further qualification. Space: O(V²) for the capacity/flow matrices as
implemented here (or O(V + E) with adjacency lists), plus O(V) each for the height and
excess arrays.
See Choosing a Network Flow Algorithm for how this page's local push/relabel model compares against Edmonds-Karp's and Dinic's global searches side by side, and when that locality is actually the deciding factor rather than raw complexity.