Introduction

Picture a network of water pipes running from a source to a destination. Every pipe has a capacity — a maximum it can carry per second. Some pipes are fat, some are thin, and they join at junctions. The question is simple: how much water can you push from the source to the destination at once?

That's the maximum flow problem, and it isn't only about water. The "pipes" can be roads carrying cars, cables carrying data, or a supply chain carrying goods. Anywhere stuff moves through a network with limited links, max flow asks for the most you can send.

Here's the twist that makes this article special. Almost every problem on this site is easy to check but hard to solve. Max flow breaks the pattern: it looks tangled and complex, yet it has a beautiful, efficient solution. Sometimes the limits of algorithms bend in our favour.

Push the Flow

Below is a small network. Water starts at S and must reach T; each pipe is labelled flow / capacity. The strategy is wonderfully simple: find any route from S to T that still has spare room, and push as much as the tightest pipe on it allows. Repeat. This is the idea of an augmenting path.

Press Find a path to send flow one route at a time, or Solve to go all the way. Watch the total climb — and then stall.

<p class="hint">Water flows from the source <b>S</b> to the sink <b>T</b>. Each pipe has a capacity (the second number; the first is how much is flowing now). Press <b>Find a path</b> to send more water along one route at a time, or <b>Solve</b> to reach the maximum. When no more can flow, the <b>bottleneck</b> (the minimum cut) lights up red.</p>
<svg id="net" viewBox="0 0 360 280" role="img" aria-label="Flow network">
  <defs>
    <marker id="arrow" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse">
      <path d="M0,0 L10,5 L0,10 z" fill="#888"></path>
    </marker>
    <marker id="arrowhi" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse">
      <path d="M0,0 L10,5 L0,10 z" fill="#e07a00"></path>
    </marker>
  </defs>
  <g id="edges"></g>
  <g id="nodes"></g>
</svg>
<p id="status" class="status"></p>
<div class="bar-btns">
  <button id="step" type="button">Find a path</button>
  <button id="solve" type="button">Solve</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .5rem; line-height: 1.45; }
svg { width: 100%; max-width: 360px; height: auto; display: block; margin: 0 auto; }
.elabel { font: 700 12px ui-monospace, monospace; fill: #333; paint-order: stroke; stroke: #fff; stroke-width: 3px; }
.nlabel { font: 700 15px system-ui; fill: #fff; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.status { font-size: 1rem; font-weight: 700; min-height: 1.4em; margin: .5rem 0; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.bar-btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Maximum flow by augmenting paths (Edmonds-Karp). Unlike the NP-hard problems on this site, max flow is solvable in polynomial time — and the maximum flow always equals the capacity of the minimum cut (the tightest bottleneck).
const NODES = { S: { x: 45, y: 140 }, A: { x: 180, y: 65 }, B: { x: 180, y: 215 }, T: { x: 315, y: 140 } };
const NAMES = Object.keys(NODES);
const baseEdges = [
  { u: 'S', v: 'A', cap: 3 }, { u: 'S', v: 'B', cap: 3 },
  { u: 'A', v: 'B', cap: 2 }, { u: 'A', v: 'T', cap: 4 }, { u: 'B', v: 'T', cap: 2 },
];
let edges, done, lastPath, cutSet;

function reset() {
  edges = baseEdges.map(e => ({ ...e, flow: 0 }));
  done = false; lastPath = []; cutSet = null;
  render();
  setStatus('Total flow: 0. Press "Find a path" to start.', false);
}

// BFS for one augmenting path in the residual graph.
function findPath() {
  const parent = {}; parent['S'] = null;
  const q = ['S'];
  while (q.length) {
    const u = q.shift();
    if (u === 'T') break;
    edges.forEach((e, i) => {
      if (e.u === u && e.cap - e.flow > 0 && !(e.v in parent)) { parent[e.v] = { i, fwd: true, from: u }; q.push(e.v); }
      if (e.v === u && e.flow > 0 && !(e.u in parent)) { parent[e.u] = { i, fwd: false, from: u }; q.push(e.u); }
    });
  }
  if (!('T' in parent)) return null;
  const steps = []; let n = 'T';
  while (parent[n]) { steps.push(parent[n]); n = parent[n].from; }
  steps.reverse();
  const bottleneck = Math.min(...steps.map(s => s.fwd ? edges[s.i].cap - edges[s.i].flow : edges[s.i].flow));
  return { steps, bottleneck };
}

function reachable() {
  const seen = { S: true }; const q = ['S'];
  while (q.length) {
    const u = q.shift();
    edges.forEach(e => {
      if (e.u === u && e.cap - e.flow > 0 && !seen[e.v]) { seen[e.v] = true; q.push(e.v); }
      if (e.v === u && e.flow > 0 && !seen[e.u]) { seen[e.u] = true; q.push(e.u); }
    });
  }
  return seen;
}

const totalFlow = () => edges.filter(e => e.u === 'S').reduce((s, e) => s + e.flow, 0)
  - edges.filter(e => e.v === 'S').reduce((s, e) => s + e.flow, 0);

function step() {
  if (done) return;
  const aug = findPath();
  if (!aug) { finish(); return; }
  aug.steps.forEach(s => { edges[s.i].flow += s.fwd ? aug.bottleneck : -aug.bottleneck; });
  lastPath = aug.steps.filter(s => s.fwd).map(s => s.i);
  render();
  const route = ['S', ...aug.steps.map(s => s.fwd ? edges[s.i].v : edges[s.i].u)].join('→');
  setStatus(fmt('Sent %bottleneck% unit(s) along %route%. Total flow: %totalFlow%.', { bottleneck: aug.bottleneck, route: route, totalFlow: totalFlow() }), false);
}

function solve() { let n = 0; while (!done && n++ < 50) step(); }

function finish() {
  done = true; lastPath = []; cutSet = reachable();
  render();
  const cut = edges.filter(e => cutSet[e.u] && !cutSet[e.v]).map(e => `${e.u}→${e.v}`).join(', ');
  setStatus(fmt('Maximum flow = %totalFlow%. No more can pass: the bottleneck (min cut) is %cut%.', { totalFlow: totalFlow(), cut: cut }), true);
}

function setStatus(t, ok) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status' + (ok ? ' ok' : ''); }

function shorten(a, b, r) {
  const dx = b.x - a.x, dy = b.y - a.y, L = Math.hypot(dx, dy);
  return { x1: a.x + dx / L * r, y1: a.y + dy / L * r, x2: b.x - dx / L * r, y2: b.y - dy / L * r, ux: dx / L, uy: dy / L };
}

function render() {
  const eg = document.getElementById('edges'); eg.innerHTML = '';
  edges.forEach((e, i) => {
    const a = NODES[e.u], b = NODES[e.v], s = shorten(a, b, 26);
    const isCut = cutSet && cutSet[e.u] && !cutSet[e.v];
    const inPath = lastPath.includes(i);
    const color = isCut ? '#e63946' : inPath ? '#e07a00' : '#bbb';
    const ln = document.createElementNS('http://www.w3.org/2000/svg', 'line');
    ln.setAttribute('x1', s.x1); ln.setAttribute('y1', s.y1); ln.setAttribute('x2', s.x2); ln.setAttribute('y2', s.y2);
    ln.setAttribute('stroke', color); ln.setAttribute('stroke-width', isCut || inPath ? 4 : 2.5);
    ln.setAttribute('marker-end', `url(#${inPath ? 'arrowhi' : 'arrow'})`);
    eg.appendChild(ln);
    const mx = (s.x1 + s.x2) / 2 - s.uy * 12, my = (s.y1 + s.y2) / 2 + s.ux * 12;
    const tx = document.createElementNS('http://www.w3.org/2000/svg', 'text');
    tx.setAttribute('x', mx); tx.setAttribute('y', my); tx.setAttribute('text-anchor', 'middle'); tx.setAttribute('class', 'elabel');
    if (e.flow > 0) tx.setAttribute('fill', '#0a7d33');
    tx.textContent = `${e.flow}/${e.cap}`;
    eg.appendChild(tx);
  });
  const ng = document.getElementById('nodes'); ng.innerHTML = '';
  NAMES.forEach(name => {
    const p = NODES[name];
    const c = document.createElementNS('http://www.w3.org/2000/svg', 'circle');
    c.setAttribute('cx', p.x); c.setAttribute('cy', p.y); c.setAttribute('r', 22);
    c.setAttribute('fill', name === 'S' ? '#2a9d8f' : name === 'T' ? '#457b9d' : '#6c757d');
    c.setAttribute('stroke', '#fff'); c.setAttribute('stroke-width', 2);
    ng.appendChild(c);
    const t = document.createElementNS('http://www.w3.org/2000/svg', 'text');
    t.setAttribute('x', p.x); t.setAttribute('y', p.y); t.setAttribute('class', 'nlabel');
    t.textContent = name;
    ng.appendChild(t);
  });
}

document.getElementById('step').addEventListener('click', step);
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

When no route has spare room left, you've hit the maximum. Notice why it stops: a set of pipes is completely full, and together they form a wall the flow can't get past. That wall is the key to the whole problem.

Max-Flow Equals Min-Cut

The wall you just hit has a name: a cut. A cut splits the network into two sides — the source's side and the sink's side — and its capacity is the total of the pipes crossing from one side to the other. The minimum cut is the cheapest such wall.

The celebrated max-flow min-cut theorem says something remarkable: the maximum flow you can push is exactly equal to the capacity of the minimum cut. The most you can send and the cheapest way to block everything are the same number.

It's a perfect example of duality — two questions that look opposite ("send the most" vs. "block with the least") turn out to be two views of one truth. In the demo, the red pipes at the end are the minimum cut: saturate them and nothing more can pass.

The Good News

Now the payoff. Max flow is not NP-hard — it sits comfortably in P, the class of problems we can solve efficiently.

  • The Ford–Fulkerson method keeps finding augmenting paths until none remain — exactly what the demo does.
  • Choosing the shortest augmenting path each time (Edmonds–Karp) guarantees it finishes in polynomial time, no matter the capacities.
  • Faster methods (Dinic's algorithm, push-relabel, and recent near-linear-time breakthroughs) make even enormous networks practical.

This is the encouraging mirror image of the P vs NP story. Max flow could have been a combinatorial nightmare — there are astronomically many ways to route flow — yet the augmenting-path insight tames it completely. A handful of beautiful ideas turn a seemingly hard problem into an everyday tool.

Where It Matters

Because so many situations are "move as much as possible through a network", max flow shows up far beyond plumbing:

  • Logistics and transport: maximize goods through a road, rail, or shipping network; find the bottleneck links.
  • Telecommunications: route the most data through a network and identify the cables that limit it.
  • Matching problems: assigning workers to jobs or students to schools becomes a max-flow problem (bipartite matching).
  • Image segmentation: computer vision separates foreground from background by computing a minimum cut on a pixel network.
  • Reliability and security: the minimum cut reveals the fewest links whose failure — or sabotage — would disconnect a network.

The min-cut side is just as useful as the max-flow side: one tells you the most you can achieve, the other tells you exactly where the weak point is.

Conclusion

Maximum flow is the optimist's problem. It looks every bit as tangled as the NP-hard puzzles elsewhere on this site, yet it yields to a single elegant idea — keep pushing along any path with room — and finishes fast every time. And as a bonus, it hands us the minimum cut: the precise bottleneck that limits everything.

It's a reminder that "looks complicated" and "is intractable" are different things. Some of the most useful problems in computing are exactly the ones that, once you find the right way to look at them, turn out to be wonderfully, provably easy.

Share this article

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

Comments

Loading comments...

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