Maximum Flow

Find augmenting paths in a residual network, push each bottleneck, and use reverse edges to reroute flow.

Core idea

A residual network records how much more flow can move forward and how much previous flow can be canceled backward. Each augmenting path pushes its smallest residual capacity.

Read the visualization

Edge labels show flow over capacity. The active path is highlighted before its bottleneck is added, and reverse residual choices preserve the ability to reroute earlier decisions.

Initialize every network edge with zero flow and its full residual capacity.

1function maxFlow(n: number, edges: [number, number, number][], s: number, t: number): number {
const cap = Array.from({ length: n }, () => new Array(n).fill(0));
for (const [u, v, c] of edges) cap[u][v] += c;    // init amount  capacity (init edge init 0)
let flow = 0;
const dfs = (u: number, pushed: number, vis: boolean[]): number => {
  if (u === t) return pushed;
  vis[u] = true;
  for (let v = 0; v < n; v++) {
    if (!vis[v] && cap[u][v] > 0) {               // augment amount  > 0 augment
      const d = dfs(v, Math.min(pushed, cap[u][v]), vis);
      if (d > 0) { cap[u][v] -= d; cap[v][u] += d; return d; } // augment flow  + augment edge augment amount 
    }
  }
  return 0;
};
for (;;) {
  const pushed = dfs(s, Infinity, new Array(n).fill(false)); // find one  count  augmenting path 
  if (pushed === 0) break;
  flow += pushed;                                 // find bottleneck 
}
return flow;
22}

source → sink: s → t
current flow: 0 / maximum 6

Complexity and tradeoffs

Time: O(EF) for integer Ford-Fulkerson. Space: O(V+E). The bound depends on maximum flow F; Edmonds-Karp or Dinic gives stronger path-selection guarantees.

Invariant: Every intermediate flow respects edge capacities and conserves flow at all vertices except the source and sink.

Where it fits

Maximum flow solves transport capacity, bipartite matching, image segmentation, and many disjoint-path problems. The final unreachable boundary also identifies a minimum cut.