---
title: Network Flow
module: Graphs
moduleNumber: 6
lessonNumber: 8
order: 608
summary: |
  How much can flow through a network from source to sink? We build flow
  networks with capacity and conservation constraints, increase a flow by
  pushing along augmenting paths in the residual graph, and see how reverse
  edges let the algorithm undo earlier routing. Ford-Fulkerson and its BFS refinement
  Edmonds-Karp find a maximum flow, traced end to end on a worked network.
topics: [Network Flow]
sources:
  - book: CLRS
    ref: "Ch. 26 — Maximum Flow"
  - book: Erickson
    ref: "Ch. 10 — Maximum Flows"
  - book: Skiena
    ref: "§6 — Weighted Graph Algorithms"
practice:
  - title: 'Minimum Number of Vertices to Reach All Nodes'
    slug: minimum-number-of-vertices-to-reach-all-nodes
    difficulty: Medium
---

Imagine a network of pipes carrying water from a source to a sink, each pipe
with a maximum capacity. How much water can you push through end to end? This is
the **maximum flow** problem, and its reach extends far past plumbing: routing
traffic, scheduling jobs, matching applicants to jobs, even segmenting images
all reduce to it. Max-flow is one of algorithm design's great _modeling_ tools;
the art, as Erickson stresses, lies in _recognizing_ a flow problem.[^erickson-flow]

## Flow networks

Think of routing a single commodity (water, electricity, traffic, money) from
a source $s$ to a sink $t$ across a network whose edges have limited throughput.

> **Definition (Flow network).** A flow network is a weighted directed graph $G = (V, E, c)$ with a
> **capacity** function $c : E \to \mathbb{R}^+$ giving each edge $(u, v)$ a
> non-negative capacity $c(u, v) \ge 0$, together with two distinguished
> vertices: a **source** $s$ and a **sink** $t$.

A **flow** is a function $f : E \to \mathbb{R}$ on the edges. The single most
useful piece of bookkeeping is the **net flow out** of a vertex $v$, written
using the boundary symbol $\partial$:

$$
\partial f(v) \;:=\; \sum_{\substack{w\, :\, (v, w) \in E}} f(v, w)
            \;-\; \sum_{\substack{u\, :\, (u, v) \in E}} f(u, v)
            \quad=\quad \text{(flow out of $v$)} - \text{(flow into $v$)}.
$$

A flow is **feasible** when it obeys two rules:

- **Non-negativity \& capacity.** $0 \le f(u, v) \le c(u, v)$ for every edge:
  no edge runs backward, and none carries more than its capacity.
- **Conservation.** $\partial f(v) = 0$ for every vertex $v \notin \set{s, t}$:
  nothing is created or destroyed at an interior node. (When conservation holds
  at _every_ vertex, $f$ is a **circulation**.)

The **value** of an $s$–$t$ flow is the net amount leaving the source,
$\abs{f} := \partial f(s)$. A short computation shows this is the same as the net
amount arriving at the sink: summing $\partial f(v)$ over _all_ vertices counts
each edge's flow once with a $+$ and once with a $-$, so
$\sum_{v \in V} \partial f(v) = 0$; conservation kills every interior term,
leaving $\partial f(s) + \partial f(t) = 0$, i.e. $\abs{f} = \partial f(s) =
-\partial f(t)$. The **maximum-flow problem** is to find a feasible flow of
greatest value.

Below is a worked network; each edge is labeled $f / c$
(flow over capacity), realizing $\abs{f} = 12$ units pushed from $s$ to $t$:

$$
% caption: A flow network with edges labeled flow over capacity, carrying a flow of value
%          12 from $s$ to $t$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=8mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  >={Stealth[round]}]
  \node[vtx] (s) at (0,0) {$s$};
  \node[vtx] (a) at (1.5,1.7) {$a$};
  \node[vtx] (b) at (3.8,1.7) {$b$};
  \node[vtx] (g) at (2.1,-1.7) {$g$};
  \node[vtx] (d) at (6.3,1.1) {$d$};
  \node[vtx] (h) at (4.9,-1.7) {$h$};
  \node[vtx] (t) at (7.7,-0.3) {$t$};
  \draw[->] (s) -- node[fl]{2/16} (b);
  \draw[->] (s) -- node[fl]{10/10} (g);
  \draw[->] (b) -- node[fl]{0/3} (a);
  \draw[->] (a) -- node[fl]{0/9} (s);
  \draw[->] (b) -- node[fl]{2/5} (d);
  \draw[->] (b) -- node[fl]{0/12} (g);
  \draw[->] (g) -- node[fl]{10/10} (h);
  \draw[->] (d) -- node[fl]{2/15} (t);
  \draw[->] (d) -- node[fl]{0/10} (h);
  \draw[->] (h) -- node[fl]{10/20} (t);
\end{tikzpicture}
$$

Conservation is the statement that each interior node _balances_. Take
vertex $b$: its incident flows are the outgoing $f_{ba} = 0$, $f_{bd} = 2$,
$f_{bg} = 0$ and the incoming $f_{sb} = 2$, so

$$
\partial f(b) \;=\; f_{ba} + f_{bd} + f_{bg} - f_{sb}
            \;=\; 0 + 2 + 0 - 2 \;=\; 0.
$$

The same check at $g$ reads $f_{gh} - (f_{sg} + f_{bg}) = 10 - (10 + 0) = 0$,
and at the source $\partial f(s) = f_{sb} + f_{sg} - f_{as} = 2 + 10 - 0 = 12
= \abs{f}$. Checking $\partial f(v) = 0$ at every interior vertex this way is
how you verify a flow is feasible.

::impl{algo="flow_network"}

## Augmenting paths and the residual graph

How do we _increase_ a flow? Find a path from $s$ to $t$ that still has spare
room and push more along it. The bookkeeping device that makes this precise,
and makes the algorithm correct, is the **residual graph**.

> **Definition (Residual graph).** Given a feasible flow $f$, the residual graph is a flow network
> $G_f = (V, E_f, c^f)$ on the same vertices, where each original edge
> contributes a **forward** residual edge (spare room to push more) and a
> **backward** residual edge (flow we could cancel):
> $$
> E_f = \underbrace{\set{(u, v) \in E : f_{uv} < c_{uv}}}_{\text{unsaturated — can carry more}}
>   \;\cup\; \underbrace{\set{(v, u) : (u, v) \in E,\; f_{uv} > 0}}_{\text{reverse — flow cancellation}}.
> $$

Concretely, each original edge $(u, v)$ splits into three cases
on its **residual capacity** $c^f$:

- If $f_{uv} = 0$ (empty), put $(u, v) \in E_f$ with $c^f_{uv} = c_{uv}$.
- If $0 < f_{uv} < c_{uv}$ (partly used), put _both_: $(u, v)$ with
  $c^f_{uv} = c_{uv} - f_{uv}$, and $(v, u)$ with $c^f_{vu} = f_{uv}$.
- If $f_{uv} = c_{uv}$ (saturated), put only the reverse $(v, u)$ with
  $c^f_{vu} = f_{uv}$.

(We assume $G$ has **no anti-parallel edges**, at most one of $(u, v)$, $(v, u)$
is in $E$, so these reverse edges are unambiguous. Any graph can be preprocessed
to satisfy this by splitting an edge through a dummy vertex.)

The backward edges are the subtle part that matters: pushing flow along $(v, u)$
_cancels_ existing flow on $(u, v)$, letting the algorithm **undo** earlier,
suboptimal decisions. That is why a greedy "fill paths until stuck"
approach can get stuck below optimum, while augmenting paths cannot. Below, the
feasible flow from the worked network (top, with vertex $a$ omitted since all
of its edges are empty) and the residual graph $G_f$ it induces (bottom); each
residual edge is labeled with its capacity $c^f_e$:

$$
% caption: A feasible flow (top) and the residual graph it induces (bottom), with
%          residual capacities labeled. Saturated edges ($s \to g$, $g \to h$) survive
%          only as reverse edges; empty edges ($b \to g$) only as forward edges.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  capt/.style={font=\scriptsize, draw=none},
  >={Stealth[round]}]
  % --- top: flow f ---
  \begin{scope}
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (b) at (1.7,0.85) {$b$};
    \node[vtx] (d) at (3.9,0.85) {$d$};
    \node[vtx] (g) at (1.7,-0.85) {$g$};
    \node[vtx] (h) at (3.9,-0.85) {$h$};
    \node[vtx] (t) at (5.5,0.05) {$t$};
    \draw[->] (s) -- node[fl, above left]{$2$} (b);
    \draw[->] (s) -- node[fl, below left]{$10$} (g);
    \draw[->] (b) -- node[fl, above]{$2$} (d);
    \draw[->] (b) -- node[fl, pos=0.45]{$0$} (g);
    \draw[->] (g) -- node[fl, below]{$10$} (h);
    \draw[->] (d) -- node[fl]{$2$} (t);
    \draw[->] (h) -- node[fl, below right]{$10$} (t);
    \node[capt] at (2.8,-1.75) {$f_e$ per edge in $G$};
  \end{scope}
  % --- below: residual graph G_f ---
  \begin{scope}[yshift=-38mm]
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (b) at (1.7,0.85) {$b$};
    \node[vtx] (d) at (3.9,0.85) {$d$};
    \node[vtx] (g) at (1.7,-0.85) {$g$};
    \node[vtx] (h) at (3.9,-0.85) {$h$};
    \node[vtx] (t) at (5.5,0.05) {$t$};
    \draw[->] (s) to[bend left=14] node[fl, above left]{$14$} (b);
    \draw[->] (b) to[bend left=14] node[fl, below right=-0.5mm]{$2$} (s); % reverse of s->b
    \draw[->] (g) to[bend left=14] node[fl, below left]{$10$} (s); % reverse of s->g (sat)
    \draw[->] (b) to[bend left=14] node[fl, above]{$3$} (d);
    \draw[->] (d) to[bend left=14] node[fl, below]{$2$} (b); % reverse of b->d
    \draw[->] (b) -- node[fl, pos=0.45]{$12$} (g);
    \draw[->] (h) to[bend left=14] node[fl, left]{$10$} (g); % reverse of g->h (sat)
    \draw[->] (d) to[bend left=14] node[fl, above right]{$13$} (t);
    \draw[->] (t) to[bend left=14] node[fl, pos=0.62, above=0.3mm]{$2$} (d); % reverse of d->t
    \draw[->] (h) to[bend left=14] node[fl, below, pos=0.55]{$10$} (t);
    \draw[->] (t) to[bend left=14] node[fl, below, pos=0.45]{$10$} (h); % reverse of h->t
    \node[capt] at (2.8,-1.75) {$c^f_e$ per edge in $G_f$};
  \end{scope}
\end{tikzpicture}
$$

> **Definition (Augmenting path).** An augmenting path is any path from $s$ to $t$ in the residual graph
> $G_f$. Its **bottleneck** is the minimum residual capacity
> $\min_{e \in P} c^f_e$ along it; pushing that much extra flow keeps $f$ feasible
> and raises $\abs{f}$ by the bottleneck.

A single augmentation is easy to picture on a small network. Each edge below is
labeled $f / c$; the highlighted residual path $s \to a \to b \to t$ has residual
capacities $\langle 1, 2, 3 \rangle$, so its bottleneck is $1$. Pushing one unit
along it saturates $s \to a$ and lifts the flow value from $5$ to $6$, with every
interior vertex still balanced:

$$
% caption: One augmentation: the residual path $s \to a \to b \to t$ has capacities
%          $\langle 1, 2, 3 \rangle$, so its bottleneck is $1$; pushing $1$ raises the
%          flow value from $5$ to $6$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \begin{scope}
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (a) at (1.8,0.9) {$a$};
    \node[vtx] (b) at (1.8,-0.9) {$b$};
    \node[vtx] (t) at (3.6,0) {$t$};
    \draw[->, acc, thick] (s) -- node[fl, above left]{3/4} (a);
    \draw[->] (s) -- node[fl, below left]{2/2} (b);
    \draw[->] (a) -- node[fl, above right]{3/3} (t);
    \draw[->, acc, thick] (a) -- node[fl]{0/2} (b);
    \draw[->, acc, thick] (b) -- node[fl, below right]{2/5} (t);
    \node[font=\footnotesize] at (1.8,-2.0) {before: value 5};
  \end{scope}
  \begin{scope}[xshift=52mm]
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (a) at (1.8,0.9) {$a$};
    \node[vtx] (b) at (1.8,-0.9) {$b$};
    \node[vtx] (t) at (3.6,0) {$t$};
    \draw[->, acc, thick] (s) -- node[fl, above left]{4/4} (a);
    \draw[->] (s) -- node[fl, below left]{2/2} (b);
    \draw[->] (a) -- node[fl, above right]{3/3} (t);
    \draw[->, acc, thick] (a) -- node[fl]{1/2} (b);
    \draw[->, acc, thick] (b) -- node[fl, below right]{3/5} (t);
    \node[font=\footnotesize] at (1.8,-2.0) {after push 1: value 6};
  \end{scope}
\end{tikzpicture}
$$

### Why the back edges matter

It is tempting to skip the reverse edges entirely: repeatedly find an $s$–$t$
path with spare _forward_ capacity, saturate it, and stop when none remains.
This greedy scheme is wrong, and the smallest counterexample shows why. Take
the diamond below, every edge of capacity $1$; its maximum flow is $2$ (route
$s \to u \to t$ and $s \to v \to t$). Suppose greedy first picks the zigzag
path $s \to u \to v \to t$ and pushes $1$ along it. Now every remaining
forward option is blocked: $s \to v$ has spare room but $v \to t$ is
saturated, and $u \to t$ has spare room but $s \to u$ is saturated. Greedy
halts at value $1$, half the optimum.

The residual graph repairs exactly this. Because $u \to v$ carries flow $1$,
$G_f$ contains the reverse edge $(v, u)$ with capacity $1$, and the path
$s \to v \to u \to t$ becomes available. Pushing $1$ along it _cancels_ the
unit on $u \to v$ (its flow drops back to $0$), rerouting the first unit
through $u \to t$ while the new unit takes $v \to t$. No water flows backward;
the algorithm has merely revised an earlier routing decision:

$$
% caption: Greedy without back edges gets stuck. Top: saturating the zigzag
%          $s \to u \to v \to t$ blocks every remaining forward path at value $1$.
%          Middle: the residual graph contains the reverse edge $(v, u)$, opening the
%          path $s \to v \to u \to t$. Bottom: pushing $1$ along it cancels the flow on
%          $u \to v$ and reaches the maximum value $2$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  capt/.style={font=\scriptsize, draw=none},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \begin{scope}
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (u) at (1.8,1.0) {$u$};
    \node[vtx] (v) at (1.8,-1.0) {$v$};
    \node[vtx] (t) at (3.6,0) {$t$};
    \draw[->, acc, thick] (s) -- node[fl, above left]{1/1} (u);
    \draw[->] (s) -- node[fl, below left]{0/1} (v);
    \draw[->, acc, thick] (u) -- node[fl]{1/1} (v);
    \draw[->] (u) -- node[fl, above right]{0/1} (t);
    \draw[->, acc, thick] (v) -- node[fl, below right]{1/1} (t);
    \node[capt] at (1.8,-1.9) {greedy push of 1: value 1};
  \end{scope}
  \begin{scope}[yshift=-34mm]
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (u) at (1.8,1.0) {$u$};
    \node[vtx] (v) at (1.8,-1.0) {$v$};
    \node[vtx] (t) at (3.6,0) {$t$};
    \draw[->] (u) -- node[fl, above left]{1} (s);
    \draw[->, acc, thick] (s) -- node[fl, below left]{1} (v);
    \draw[->, acc, thick] (v) -- node[fl]{1} (u);
    \draw[->, acc, thick] (u) -- node[fl, above right]{1} (t);
    \draw[->] (t) -- node[fl, below right]{1} (v);
    \node[capt] at (1.8,-1.9) {residual $G_f$: the undo path};
  \end{scope}
  \begin{scope}[yshift=-68mm]
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (u) at (1.8,1.0) {$u$};
    \node[vtx] (v) at (1.8,-1.0) {$v$};
    \node[vtx] (t) at (3.6,0) {$t$};
    \draw[->, acc, thick] (s) -- node[fl, above left]{1/1} (u);
    \draw[->, acc, thick] (s) -- node[fl, below left]{1/1} (v);
    \draw[->] (u) -- node[fl]{0/1} (v);
    \draw[->, acc, thick] (u) -- node[fl, above right]{1/1} (t);
    \draw[->, acc, thick] (v) -- node[fl, below right]{1/1} (t);
    \node[capt] at (1.8,-1.9) {max f\/low: value 2};
  \end{scope}
\end{tikzpicture}
$$

> **Takeaway.** Reverse residual edges are the algorithm's undo button. A path
> through a reverse edge does not push flow backward along a pipe; it cancels
> a previous routing choice and re-spends that capacity elsewhere. Without
> them, path-pushing is a greedy heuristic that can stall arbitrarily far
> below the maximum.

## The augmentation lemma

Before trusting the algorithm we must prove that augmenting actually produces a
_better feasible flow_. Augmenting $f$ along a path $P$ by amount $k$ produces a
new function $f'$ defined edge-by-edge:

$$
f'_{uv} =
\begin{cases}
f_{uv} + k, & \text{if } (u, v) \text{ on } P,\\
f_{uv} - k, & \text{if } (v, u) \text{ on } P,\\
f_{uv}, & \text{otherwise (neither $(u,v)$ nor $(v,u)$ on $P$).}
\end{cases}
$$

> **Lemma (Augmentation).** If $P$ is an $s$–$t$ path in $G_f$ and
> $0 < k \le \min_{e \in P} c^f_e$, then $f'$ is a feasible $s$–$t$ flow of value
> $\abs{f'} = \abs{f} + k$.

> **Proof.** Four short claims, each just unfolding the definitions.
>
> - **Non-negativity** ($f'_{uv} \ge 0$). The only danger is a decrease,
>   $f'_{uv} = f_{uv} - k$, which happens when the reverse $(v, u)$ lies on $P$. But
>   then $(v, u) \in E_f$ forces $c^f_{vu} = f_{uv}$, and $k \le c^f_{vu} = f_{uv}$,
>   so $f'_{uv} = f_{uv} - k \ge 0$.
> - **Capacity** ($f'_{uv} \le c_{uv}$). The only danger is an increase,
>   $f'_{uv} = f_{uv} + k$, which happens when $(u, v)$ lies on $P$. Then $(u, v) \in
>   E_f$ forces $c^f_{uv} = c_{uv} - f_{uv}$, and $k \le c^f_{uv}$, so
>   $f'_{uv} = f_{uv} + k \le f_{uv} + (c_{uv} - f_{uv}) = c_{uv}$.
> - **Conservation** ($\partial f'(v) = 0$ for $v \notin \set{s, t}$). If $v \notin
>   P$, none of its incident terms change. If $v$ is an interior vertex of $P$, the
>   path enters $v$ once and leaves once; that pair of edges shifts the in- and
>   out-flow by the _same_ $k$ (with matching signs whether the path step is a
>   forward or reverse edge), so $\partial f'(v) = \partial f(v) = 0$.
> - **Value** ($\abs{f'} = \abs{f} + k$). $P$ uses exactly one edge out of $s$ and
>   none into $s$. That single edge gains $k$ (forward) or loses $-k$ across a
>   reverse step, so $\partial f'(s) = \partial f(s) + k$, i.e. $\abs{f'} = \abs{f} +
>   k$. $\qed$

So every augmentation strictly increases the value while keeping $f$ legal.
The converse, which the min-cut proof will need, also holds: if $f$ is **not**
maximum, $G_f$ must contain an augmenting path. Putting the two together gives
the equivalence at the center of the theory

$$
\ \exists\ s\text{–}t \text{ path in } G_f
   \iff \abs{f} \text{ is not maximum.}\ 
$$

## Ford-Fulkerson and Edmonds-Karp

The $\textsc{Ford-Fulkerson}$ method is then simple: while an augmenting
path exists, push flow along it.[^clrs-ff]

```algorithm
caption: $\textsc{Ford-Fulkerson}(G, s, t)$ — augment until no path remains
number: 1
foreach edge $(u, v) \in E$ do
  $f(u, v) \gets 0$
while there exists an augmenting path $p$ from $s$ to $t$ in $G_f$ do
  $c_f(p) \gets \min\set{c_f(u, v) : (u, v) \text{ on } p}$ // bottleneck
  foreach edge $(u, v)$ on $p$ do
    $f(u, v) \gets f(u, v) + c_f(p)$ // push forward
    $f(v, u) \gets f(v, u) - c_f(p)$ // cancel on reverse edge
return $f$
```

> **Correctness** is immediate from the augmentation lemma: each iteration produces
> a feasible flow of strictly larger value, and the method halts exactly when no
> augmenting path remains, which (by the equivalence above, proved in full
> below) is the condition for a maximum flow.

**Running time** rests on an invariant: if every capacity is an integer,
$c : E \to \mathbb{N}$, then _all residual capacities $c^f_e$ and flow values
$f_{uv}$ stay integers_ throughout. Each augmentation then raises $\abs{f}$ by at
least $1$, so there are at most $\abs{f^\ast}$ iterations, each costing $O(m)$ to
find a path and push along it (here $m = \abs{E}$, $n = \abs{V}$):

$$
T(m, n) \;\le\; (\#\text{iters}) \cdot O(m) \;\le\; \abs{f^\ast} \cdot O(m)
        \;=\; O\!\parens{m \, \abs{f^\ast}}.
$$

If additionally every capacity lies in $[1, C]$, then $\abs{f^*} \le \sum_{e} c_e
\le Cm$, giving $T(m, n, C) = O(m^2 C)$. This is
[_pseudo-polynomial_](/algorithms/foundations/asymptotic-analysis): fine for
small capacities, but very slow when they are huge. The classic bad
case has a middle edge of capacity $1$ between two paths of capacity $1000$; a
naïve solver alternately pushes one unit forward and one unit back, taking
$\Omega(C)$ augmentations. (On irrational capacities the method may not even
terminate.)

$$
% caption: The Ford-Fulkerson bad case: a unit middle edge between two capacity-$1000$
%          paths. A poor path choice alternately pushes one unit forward and back, taking
%          $\Omega(C)$ augmentations.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=8mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \node[vtx] (s) at (0,0) {$s$};
  \node[vtx] (u) at (2.2,1.2) {$u$};
  \node[vtx] (v) at (2.2,-1.2) {$v$};
  \node[vtx] (t) at (4.4,0) {$t$};
  \draw[->] (s) -- node[fl, above left]{$1000$} (u);
  \draw[->] (s) -- node[fl, below left]{$1000$} (v);
  \draw[->] (u) -- node[fl, above right]{$1000$} (t);
  \draw[->] (v) -- node[fl, below right]{$1000$} (t);
  \draw[->, red!80!black, thick] (u) -- node[fl]{$1$} (v);
\end{tikzpicture}
$$

The fix, due to $\textsc{Edmonds-Karp}$, is to always pick the _shortest_ augmenting
path (fewest edges): find it with [**BFS**](/algorithms/graphs/representations-and-traversal)
in the residual graph.

```algorithm
caption: $\textsc{Edmonds-Karp}(G, s, t)$ — Ford-Fulkerson with BFS path choice
number: 2
foreach edge $(u, v) \in E$ do
  $f(u, v) \gets 0$
while BFS finds a shortest path $p$ from $s$ to $t$ in $G_f$ do
  augment $f$ along $p$ by its bottleneck $c_f(p)$
return $f$
```

Why should the _shortest_ path be any better? The analysis rests on a
monotonicity property of BFS levels in the residual graph. Write
$\delta_f(v)$ for the number of edges on a shortest $s \to v$ path in $G_f$.

> **Lemma (Monotone BFS distances).** Over the run of $\textsc{Edmonds-Karp}$,
> $\delta_f(v)$ never decreases for any vertex $v$: augmenting along a shortest
> path can only push vertices to the same level or a later one.

> **Proof sketch.** Augmenting along a shortest path $p$ changes $G_f$ in only
> two ways: it may _delete_ residual edges on $p$ (the saturated ones), and it
> may _add_ the reverses of edges on $p$. Deleting edges never shortens any
> path. Each added reverse edge $(v, u)$ points from level $\delta_f(v)$ back
> to level $\delta_f(u) = \delta_f(v) - 1$, one step _backward_ along the BFS
> layering; a path that uses it spends two extra edges (one down, one back up)
> compared to staying inside the layering, so it cannot create a shortcut.
> Formally one assumes some $\delta$ decreases, picks the vertex $v$ with the
> smallest new value $\delta_{f'}(v)$, and derives a contradiction from its
> predecessor on the new shortest path (CLRS gives the full argument as Lemma
> 26.7).[^clrs-ek] $\qed$

Counting iterations now follows from a charging argument on **critical
edges**. In each augmentation, at least one residual edge $(u, v)$ on the path
has $c^f_{uv}$ equal to the bottleneck; that edge is _critical_ and disappears
from $G_f$. For $(u, v)$ to become critical again, the reverse $(v, u)$ must
first appear on some later shortest path, which requires $\delta_f(v) =
\delta_f(u) + 1$ at the first event and $\delta_{f'}(u) = \delta_{f'}(v) + 1$
at the second. With the monotone lemma,

$$
\delta_{f'}(u) \;=\; \delta_{f'}(v) + 1 \;\ge\; \delta_f(v) + 1
              \;=\; \delta_f(u) + 2,
$$

so $u$'s level rises by at least $2$ between consecutive criticalities of
$(u, v)$. Levels live in $\set{0, 1, \dots, n-1}$ (once $\delta_f(u) > n - 1$
the vertex is unreachable and the edge never reappears on a path), so each of
the at most $2m$ residual edges is critical $O(n)$ times, giving $O(mn)$
augmentations in total. Each iteration is one BFS plus one path update, $O(m)$
work, for a strongly polynomial bound _independent of capacities_:

$$
T(m, n) \;=\; O(mn) \text{ iterations} \times O(m) \text{ per iteration}
        \;=\; O(m^2 n) \;=\; O(V E^2).
$$

For dense graphs this is far from the last word — Orlin's 2012 algorithm runs
in $O(mn)$, and you may cite max-flow as an $O(mn)$ black box — but
$\textsc{Edmonds-Karp}$ is the version to know: two ideas (residual graph,
BFS) and a clean proof.

::impl{algo="ford_fulkerson,edmonds_karp"}

## A complete run of Edmonds-Karp

Here is one full run, end to end.
The network below has six vertices and seven edges (capacities on the edges);
we run $\textsc{Edmonds-Karp}$ from the zero flow, scanning neighbors in
alphabetical order so the BFS choices are reproducible. Each round we show the
residual graph, the shortest augmenting path BFS finds (highlighted), and the
bottleneck it pushes.

**Round 1.** With $f = 0$ the residual graph _is_ $G$: every edge appears
forward at full capacity. BFS layers the vertices $s \mid a, c \mid b, d \mid
t$ and returns the length-$3$ path $s \to a \to b \to t$. Its residual
capacities are $\langle 8, 5, 6 \rangle$, so the bottleneck is
$\min(8, 5, 6) = 5$: push $5$, and the value rises $0 \to 5$.

**Round 2.** Edge $a \to b$ is now saturated and survives only as the reverse
edge $(b, a)$; $s \to a$ keeps forward capacity $8 - 5 = 3$ plus a reverse
edge of capacity $5$. BFS finds $s \to a \to d \to t$ with residual
capacities $\langle 3, 3, 8 \rangle$; the bottleneck is $3$. Push $3$: the
value rises $5 \to 8$, and both $s \to a$ and $a \to d$ saturate.

$$
% caption: Rounds 1 and 2. Top: the initial residual graph (equal to $G$) with the
%          first BFS path $s \to a \to b \to t$ highlighted; its bottleneck is
%          $\min(8,5,6) = 5$. Bottom: the residual graph after pushing 5, with the
%          second path $s \to a \to d \to t$ highlighted; its bottleneck is
%          $\min(3,3,8) = 3$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  capt/.style={font=\scriptsize, draw=none},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \begin{scope}
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (a) at (2,1.1) {$a$};
    \node[vtx] (c) at (2,-1.1) {$c$};
    \node[vtx] (b) at (4.4,1.1) {$b$};
    \node[vtx] (d) at (4.4,-1.1) {$d$};
    \node[vtx] (t) at (6.4,0) {$t$};
    \draw[->, acc, thick] (s) -- node[fl, above left]{8} (a);
    \draw[->] (s) -- node[fl, below left]{6} (c);
    \draw[->, acc, thick] (a) -- node[fl, above]{5} (b);
    \draw[->] (a) -- node[fl, pos=0.38]{3} (d);
    \draw[->] (c) -- node[fl, below]{7} (d);
    \draw[->, acc, thick] (b) -- node[fl, above right]{6} (t);
    \draw[->] (d) -- node[fl, below right]{8} (t);
    \node[capt] at (3.2,-2.0) {round 1: push 5};
  \end{scope}
  \begin{scope}[yshift=-42mm]
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (a) at (2,1.1) {$a$};
    \node[vtx] (c) at (2,-1.1) {$c$};
    \node[vtx] (b) at (4.4,1.1) {$b$};
    \node[vtx] (d) at (4.4,-1.1) {$d$};
    \node[vtx] (t) at (6.4,0) {$t$};
    \draw[->, acc, thick] (s) to[bend left=12] node[fl, above left]{3} (a);
    \draw[->] (a) to[bend left=12] node[fl, below right=-0.5mm]{5} (s);
    \draw[->] (s) -- node[fl, below left]{6} (c);
    \draw[->] (b) -- node[fl, above]{5} (a);
    \draw[->, acc, thick] (a) -- node[fl, pos=0.38]{3} (d);
    \draw[->] (c) -- node[fl, below]{7} (d);
    \draw[->] (b) to[bend left=12] node[fl, above right]{1} (t);
    \draw[->] (t) to[bend left=12] node[fl, below left=-0.5mm]{5} (b);
    \draw[->, acc, thick] (d) -- node[fl, below right]{8} (t);
    \node[capt] at (3.2,-2.0) {round 2: push 3};
  \end{scope}
\end{tikzpicture}
$$

**Round 3.** The source's only remaining forward edge is $s \to c$. BFS finds
$s \to c \to d \to t$ with residual capacities $\langle 6, 7, 5 \rangle$
(edge $d \to t$ has $8 - 3 = 5$ left); the bottleneck is $5$. Push $5$: the
value rises $8 \to 13$, and $d \to t$ saturates.

**Round 4 (halt).** BFS from $s$ now reaches $c$ (forward capacity $1$
remains on $s \to c$), then $d$ (via $c \to d$, capacity $2$), then $a$ (via
the _reverse_ edge $(d, a)$) — and stops. Every edge out of this set is
saturated, so $t$ is unreachable and the algorithm halts with $\abs{f^\ast} = 13$.

$$
% caption: Rounds 3 and 4. Top: the residual graph after round 2, with the third path
%          $s \to c \to d \to t$ highlighted; its bottleneck is $\min(6,7,5) = 5$.
%          Bottom: the final residual graph. The shaded vertices $\{s, a, c, d\}$ are
%          exactly those reachable from $s$; $t$ is not among them, so no augmenting
%          path remains.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  rvtx/.style={circle, draw, fill=acc!8, minimum size=7mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  capt/.style={font=\scriptsize, draw=none},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \begin{scope}
    \node[vtx] (s) at (0,0) {$s$};
    \node[vtx] (a) at (2,1.1) {$a$};
    \node[vtx] (c) at (2,-1.1) {$c$};
    \node[vtx] (b) at (4.4,1.1) {$b$};
    \node[vtx] (d) at (4.4,-1.1) {$d$};
    \node[vtx] (t) at (6.4,0) {$t$};
    \draw[->] (a) -- node[fl, above left]{8} (s);
    \draw[->, acc, thick] (s) -- node[fl, below left]{6} (c);
    \draw[->] (b) -- node[fl, above]{5} (a);
    \draw[->] (d) -- node[fl, pos=0.38]{3} (a);
    \draw[->, acc, thick] (c) -- node[fl, below]{7} (d);
    \draw[->] (b) to[bend left=12] node[fl, above right]{1} (t);
    \draw[->] (t) to[bend left=12] node[fl, below left=-0.5mm]{5} (b);
    \draw[->, acc, thick] (d) to[bend left=12] node[fl, above left]{5} (t);
    \draw[->] (t) to[bend left=12] node[fl, below right=-0.5mm]{3} (d);
    \node[capt] at (3.2,-2.0) {round 3: push 5};
  \end{scope}
  \begin{scope}[yshift=-42mm]
    \node[rvtx] (s) at (0,0) {$s$};
    \node[rvtx] (a) at (2,1.1) {$a$};
    \node[rvtx] (c) at (2,-1.1) {$c$};
    \node[vtx] (b) at (4.4,1.1) {$b$};
    \node[rvtx] (d) at (4.4,-1.1) {$d$};
    \node[vtx] (t) at (6.4,0) {$t$};
    \draw[->] (a) -- node[fl, above left]{8} (s);
    \draw[->] (s) to[bend left=12] node[fl, above right=-0.5mm]{1} (c);
    \draw[->] (c) to[bend left=12] node[fl, below left]{5} (s);
    \draw[->] (b) -- node[fl, above]{5} (a);
    \draw[->] (d) -- node[fl, pos=0.38]{3} (a);
    \draw[->] (c) to[bend left=12] node[fl, above]{2} (d);
    \draw[->] (d) to[bend left=12] node[fl, below]{5} (c);
    \draw[->] (b) to[bend left=12] node[fl, above right]{1} (t);
    \draw[->] (t) to[bend left=12] node[fl, below left=-0.5mm]{5} (b);
    \draw[->] (t) -- node[fl, below right]{8} (d);
    \node[capt] at (3.2,-2.0) {halt: no path to $t$};
  \end{scope}
\end{tikzpicture}
$$

The whole run in one table:

| Round | Augmenting path             | Residual capacities       | Bottleneck | Value      |
| ----- | --------------------------- | ------------------------- | ---------- | ---------- |
| 1     | $s \to a \to b \to t$       | $\langle 8, 5, 6 \rangle$ | $5$        | $0 \to 5$  |
| 2     | $s \to a \to d \to t$       | $\langle 3, 3, 8 \rangle$ | $3$        | $5 \to 8$  |
| 3     | $s \to c \to d \to t$       | $\langle 6, 7, 5 \rangle$ | $5$        | $8 \to 13$ |
| 4     | none — $t$ unreachable      | —                         | —          | $13$       |

The final flow, edge by edge: $f_{sa} = 8$, $f_{sc} = 5$, $f_{ab} = 5$,
$f_{ad} = 3$, $f_{cd} = 5$, $f_{bt} = 5$, $f_{dt} = 8$. Every interior vertex
balances ($a$: in $8$, out $5 + 3$; $c$: in $5$, out $5$; $b$: in $5$, out
$5$; $d$: in $3 + 5$, out $8$), and $\abs{f^\ast} = 8 + 5 = 13$. Is $13$ really
the maximum? The halting condition says yes, but the certificate that _proves_
it is a cut — the subject of the next lesson, where this same network returns.

This continues in [Max-Flow Min-Cut and Applications](/algorithms/graphs/max-flow-min-cut). There we prove _why_ the halting flow is optimal — the max-flow min-cut theorem — and apply the abstraction to bipartite matching and a catalog of modeling reductions.

[^erickson-flow]: **Erickson**, Ch. 10 & 11 — Maximum Flows and Applications — the art of recognizing a problem as a flow problem.
[^clrs-ff]: **CLRS**, Ch. 26 — Maximum Flow — the Ford-Fulkerson method augmenting along residual paths.
[^clrs-ek]: **CLRS**, Ch. 26 — Maximum Flow — the Edmonds-Karp analysis via monotone shortest-path distances in the residual graph.