Introduction

Imagine a water distribution network: pipes connect junctions, each pipe has a maximum capacity, and you want to move as much water as possible from a source to a sink. This is the maximum flow problem — one of the most fundamental in all of combinatorial optimization.

The classic approach, Ford-Fulkerson (1956), finds a path from source to sink with leftover capacity and pushes flow along it, repeating until no such path exists. It works, but on dense graphs with many edges the repeated global path searches are expensive.

In 1988 Andrew Goldberg and Robert Tarjan introduced push-relabel, a fundamentally different strategy. Instead of looking for end-to-end paths, the algorithm:

  1. Preflows the source — it immediately saturates all outgoing edges of the source, creating "excess" flow at neighbors.
  2. Assigns every node a height label (a non-negative integer). Flow may only be pushed downhill (from a node to a neighbor with a strictly lower label).
  3. Repeatedly pushes excess from an active node (one with excess > 0) to a lower neighbor, or relabels the node (raises its height) when no downhill neighbor exists.
  4. Terminates when no active nodes remain — any excess that could not reach the sink flows back to the source, and the net flow into the sink equals the maximum flow.

The result is an algorithm that achieves O(V2E)O(V^{2}E) time in general, and O(V3)O(V^{3}) with the FIFO selection rule — both better than Ford-Fulkerson's O(VE2)O(VE^{2}) on dense graphs.

Compare it with the path-by-path approach in our max-flow article: push-relabel trades global path searches for local, node-by-node operations, and wins on graphs where E is large relative to V.

Try It

The demo below shows a six-node flow network (S → A, B → C, D → T) with capacities on each edge. Click Step to advance the algorithm one operation at a time, or Run to animate it to completion. The height of each node is shown inside its circle; orange nodes carry excess flow.

<p class="hint">A six-node flow network. Each edge shows <b>flow / capacity</b>. Orange nodes carry excess. Click <b>Step</b> to run one push or relabel, or <b>Run</b> to animate.</p>
<div class="canvas-wrap"><canvas id="c" width="520" height="300"></canvas></div>
<div class="status" id="status">Ready. Press Step or Run.</div>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.canvas-wrap { overflow-x: auto; }
canvas { display: block; border-radius: 10px; background: #f4f7fa; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.done { color: #1d3557; }
.status.active { color: #b86a00; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Push-Relabel (generic) on a 6-node network: S=0, A=1, B=2, C=3, D=4, T=5
// Edges: [from, to, capacity]
const NODE_LABELS = ['S','A','B','C','D','T'];
const N = 6;
const S = 0, T = 5;

// Positions on 520x300 canvas
const POS = [
  [60, 150],   // S
  [180, 70],   // A
  [180, 230],  // B
  [340, 70],   // C
  [340, 230],  // D
  [460, 150],  // T
];

// Raw edges [from, to, cap]
const RAW_EDGES = [
  [S, 1, 15], // S->A  cap 15
  [S, 2, 10], // S->B  cap 10
  [1, 3, 12], // A->C  cap 12
  [1, 2,  4], // A->B  cap 4
  [2, 4, 10], // B->D  cap 10
  [3, T, 10], // C->T  cap 10
  [4, 3,  6], // D->C  cap 6
  [4, T, 10], // D->T  cap 10
];

// Build adjacency list with reverse edges (for residual graph)
// edge object: { to, cap, flow, rev } where rev is index in adj[to]
function buildGraph() {
  const adj = Array.from({length: N}, () => []);
  function addEdge(u, v, cap) {
    adj[u].push({ to: v, cap, flow: 0, rev: adj[v].length });
    adj[v].push({ to: u, cap: 0, flow: 0, rev: adj[u].length - 1 });
  }
  for (const [u, v, c] of RAW_EDGES) addEdge(u, v, c);
  return adj;
}

// State
let adj, height, excess, log, animTimer, done;

function initState() {
  adj = buildGraph();
  height = new Array(N).fill(0);
  excess = new Array(N).fill(0);
  height[S] = N; // source starts at height N
  log = [];
  done = false;

  // Preflow: saturate all edges from S
  for (const e of adj[S]) {
    if (e.cap > 0) {
      const d = e.cap;
      e.flow += d;
      adj[e.to][e.rev].flow -= d;
      excess[e.to] += d;
      excess[S] -= d;
      log.push(fmt('Preflow: push %d% units S→%v% (saturate)', { d: d, v: NODE_LABELS[e.to] }));
    }
  }
}

// One push-relabel step: find first active node (not S, not T, excess>0)
// return description string or null if done
function step() {
  // Find active node
  let u = -1;
  for (let v = 0; v < N; v++) {
    if (v !== S && v !== T && excess[v] > 0) { u = v; break; }
  }
  if (u === -1) return null; // done

  // Try to push
  for (const e of adj[u]) {
    const residual = e.cap - e.flow;
    if (residual > 0 && height[u] === height[e.to] + 1) {
      const d = Math.min(excess[u], residual);
      e.flow += d;
      adj[e.to][e.rev].flow -= d;
      excess[u] -= d;
      excess[e.to] += d;
      return fmt('Push %d% units %v%→%v2% (h=%v3%→%v4%)', { d: d, v: NODE_LABELS[u], v2: NODE_LABELS[e.to], v3: height[u], v4: height[e.to] });
    }
  }

  // No push possible: relabel
  const oldH = height[u];
  let minH = Infinity;
  for (const e of adj[u]) {
    if (e.cap - e.flow > 0) minH = Math.min(minH, height[e.to]);
  }
  if (minH === Infinity) {
    // Isolated with excess: shouldn't happen in valid flow network but guard it
    return fmt('Node %v% isolated (excess %v2% stuck)', { v: NODE_LABELS[u], v2: excess[u] });
  }
  height[u] = minH + 1;
  return fmt('Relabel %v%: h %oldH% → %v2%', { v: NODE_LABELS[u], oldH: oldH, v2: height[u] });
}

// ── Drawing ──────────────────────────────────────────────────────────────────
const COLORS = {
  node: '#1d3557',
  nodeActive: '#e07b00',
  nodeS: '#2a7d4f',
  nodeT: '#7b2d8b',
  edgeFull: '#c92f3c',
  edgePart: '#457b9d',
  edgeEmpty: '#cdd9e3',
  text: '#fff',
  edgeLabel: '#1d3557',
};

function drawArrow(ctx, x1, y1, x2, y2, color, lineWidth) {
  const dx = x2 - x1, dy = y2 - y1;
  const len = Math.sqrt(dx*dx + dy*dy);
  const ux = dx/len, uy = dy/len;
  const r = 24; // node radius
  const sx = x1 + ux*r, sy = y1 + uy*r;
  const ex = x2 - ux*r, ey = y2 - uy*r;

  ctx.beginPath();
  ctx.moveTo(sx, sy);
  ctx.lineTo(ex, ey);
  ctx.strokeStyle = color;
  ctx.lineWidth = lineWidth;
  ctx.stroke();

  // arrowhead
  const al = 10, aw = 5;
  const ax1 = ex - ux*al - uy*aw, ay1 = ey - uy*al + ux*aw;
  const ax2 = ex - ux*al + uy*aw, ay2 = ey - uy*al - ux*aw;
  ctx.beginPath();
  ctx.moveTo(ex, ey);
  ctx.lineTo(ax1, ay1);
  ctx.lineTo(ax2, ay2);
  ctx.closePath();
  ctx.fillStyle = color;
  ctx.fill();
}

function draw() {
  const canvas = document.getElementById('c');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Draw edges (only forward raw edges for clarity)
  ctx.font = '12px ui-monospace, monospace';
  ctx.textAlign = 'center';
  ctx.textBaseline = 'middle';

  const drawn = new Set();
  for (const [u, v] of RAW_EDGES.map(e => [e[0], e[1]])) {
    const key = `${u}-${v}`;
    if (drawn.has(key)) continue;
    drawn.add(key);

    // Find the forward edge in adj
    let e = adj[u].find(x => x.to === v && x.cap > 0);
    if (!e) continue;

    const ratio = e.flow / e.cap;
    const color = ratio >= 1 ? COLORS.edgeFull : ratio > 0 ? COLORS.edgePart : COLORS.edgeEmpty;
    const lw = 1.5 + ratio * 2;

    const [x1, y1] = POS[u];
    const [x2, y2] = POS[v];
    drawArrow(ctx, x1, y1, x2, y2, color, lw);

    // Edge label: flow/cap
    const mx = (x1 + x2) / 2, my = (y1 + y2) / 2;
    const nx = -(y2 - y1) / Math.hypot(x2-x1, y2-y1) * 14;
    const ny = (x2 - x1) / Math.hypot(x2-x1, y2-y1) * 14;
    ctx.fillStyle = COLORS.edgeLabel;
    ctx.fillText(`${e.flow}/${e.cap}`, mx + nx, my + ny);
  }

  // Draw nodes
  for (let v = 0; v < N; v++) {
    const [x, y] = POS[v];
    const isActive = v !== S && v !== T && excess[v] > 0;
    const color = v === S ? COLORS.nodeS : v === T ? COLORS.nodeT : isActive ? COLORS.nodeActive : COLORS.node;

    ctx.beginPath();
    ctx.arc(x, y, 24, 0, 2 * Math.PI);
    ctx.fillStyle = color;
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.stroke();

    // Node label
    ctx.fillStyle = COLORS.text;
    ctx.font = 'bold 14px system-ui, sans-serif';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(NODE_LABELS[v], x, y - 5);

    // Height label
    ctx.font = '11px ui-monospace, monospace';
    ctx.fillText(`h=${height[v]}`, x, y + 8);

    // Excess label (below node)
    if (excess[v] !== 0) {
      ctx.fillStyle = '#222';
      ctx.font = '11px ui-monospace, monospace';
      ctx.fillText(`e=${excess[v]}`, x, y + 34);
    }
  }

  // Max-flow value
  const flowVal = adj[S].reduce((s, e) => s + Math.max(0, e.flow), 0);
  ctx.fillStyle = '#1d3557';
  ctx.font = 'bold 13px system-ui, sans-serif';
  ctx.textAlign = 'left';
  ctx.fillText(fmt('Max flow so far: %flowVal%', { flowVal: flowVal }), 8, 16);
}

function setStatus(t, cls) {
  const el = document.getElementById('status');
  el.textContent = t;
  el.className = 'status ' + (cls || '');
}

function doStep() {
  if (done) return;
  const msg = step();
  if (msg === null) {
    const flowVal = adj[S].reduce((s, e) => s + Math.max(0, e.flow), 0);
    setStatus(fmt('Done! Maximum flow = %flowVal%', { flowVal: flowVal }), 'ok');
    done = true;
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-run').disabled = true;
  } else {
    setStatus(msg, 'active');
  }
  draw();
}

function runAnim() {
  if (done) return;
  document.getElementById('btn-step').disabled = true;
  document.getElementById('btn-run').disabled = true;
  animTimer = setInterval(() => {
    doStep();
    if (done) clearInterval(animTimer);
  }, 500);
}

function reset() {
  clearInterval(animTimer);
  initState();
  done = false;
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
  setStatus('Ready. Press Step or Run.', '');
  draw();
}

document.getElementById('btn-step').addEventListener('click', doStep);
document.getElementById('btn-run').addEventListener('click', runAnim);
document.getElementById('btn-reset').addEventListener('click', reset);

// Boot
initState();
draw();

// Verify: run full algorithm and log result
(function verify() {
  const savedAdj = adj, savedH = height, savedE = excess, savedDone = done;
  initState();
  let iterations = 0;
  while (true) {
    const msg = step();
    if (msg === null) break;
    if (++iterations > 10000) { console.error('Push-relabel: too many iterations'); break; }
  }
  const flowVal = adj[S].reduce((s, e) => s + Math.max(0, e.flow), 0);
  console.log('Push-relabel verification: max flow =', flowVal, '(expected 20)');
  console.assert(flowVal === 20, 'Max flow should be 20');
  adj = savedAdj; height = savedH; excess = savedE; done = savedDone;
  initState(); draw();
})();
Result
Console

Watch how excess accumulates near the source before gradually flowing — or being pushed back — through the network. Each relabel raises a node's height when it has no downhill neighbor to receive its excess. The algorithm terminates when only S and T carry non-zero flow balance.

The Real Complexity

Push-relabel's performance is proven (not conjectured) and rests on tight bounds for the two operations:

  • Relabels: each node can be relabeled at most 2V − 1 times before its height exceeds 2V (the upper bound that prevents infinite loops). Total relabels ≤ 2V22V^{2}.
  • Saturating pushes: a push from u to v is saturating when it empties the edge capacity. Before u can push to v again, v must be relabeled above u, then u above v — at least 2 relabels per edge direction. Total saturating pushes ≤ 2VE.
  • Non-saturating pushes: the tricky part. Each non-saturating push moves excess to a lower node; a potential-function argument shows at most O(V2E)O(V^{2}E) such pushes total.
  • Combined: O(V2E)O(V^{2}E) overall.

With the FIFO selection rule (always process the oldest active node in a queue), the non-saturating push bound drops to O(V3)O(V^{3}) — independent of E, which makes it ideal for very dense graphs (E ≈ V2V^{2}).

Comparison with classical algorithms:

Algorithm Time complexity Best for
Ford-Fulkerson (BFS / Edmonds-Karp) O(VE2)O(VE^{2}) Sparse, unit-capacity
Push-Relabel (generic) O(V2E)O(V^{2}E) Dense graphs
Push-Relabel (FIFO) O(V3)O(V^{3}) Very dense (E ≈ V2V^{2})
King-Rao-Tarjan (1994) O(VE log(V2V^{2}/E)) Theory optimal

Status: solved. Maximum flow is in P. The push-relabel algorithm is a practical workhorse used in production implementations of maximum-flow solvers, and its O(V3)O(V^{3}) bound was proved by Goldberg & Tarjan in their landmark 1988 paper.

Where It Matters

Maximum flow is one of the most-reduced-to problems in combinatorial optimization. Push-relabel, being faster on dense graphs, is the implementation of choice in many real settings:

  • Image segmentation: cutting an image into foreground/background is a minimum-cut problem (equivalent to max-flow by the max-flow min-cut theorem). Dense pixel grids make push-relabel the standard choice here.
  • Bipartite matching: finding the maximum matching in a bipartite graph reduces to max-flow in a network with V + E nodes and edges.
  • Project selection and closure problems: which projects to fund (given dependencies and profits) is a max-flow / min-cut problem on a DAG.
  • Network routing: routing bandwidth in telecommunications and data-center networks uses max-flow to saturate links.
  • Scheduling and resource allocation: assigning tasks to machines respecting capacity constraints reduces to flow problems that push-relabel solves efficiently.

Whenever you encounter a "capacity-constrained routing" or "binary label assignment" problem, max-flow — and likely push-relabel — is lurking underneath. Understanding push-relabel means you can reduce to it and get a provably optimal solution in polynomial time.

Conclusion

Push-relabel stands as a lesson in algorithmic thinking: the obvious strategy (find a path, push flow along it) is not always the fastest. By abandoning global path searches in favor of purely local operations — push excess downhill, raise height when stuck — Goldberg and Tarjan achieved a provably better bound for dense networks.

The O(V3)O(V^{3}) FIFO variant in particular is a reminder that the right data structure and selection rule can improve a complexity class without changing the underlying algorithm idea. And behind every image-segmentation pipeline, every scheduling optimizer, and every network router that finds the true optimum lies the same elegant insight: saturate locally, correct globally, and the max-flow emerges.

Maximum flow is in P — it is one of the algorithmic success stories. But linear programming duality shows that even "easy" problems can have surprisingly rich structure. Push-relabel is where that structure becomes beautifully concrete.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/push-relabel/Content licensed under CC BY-NC 4.0.