EDMONDS-KARP: use BFS to find shortest augmenting path
§2 — The Idea, Step by Step
Picture the one-way streets between your home and your school. Every street has a limit — so many cars per minute before it jams. You want the largest steady stream of cars that can flow from home all the way to school. No matter how wide some streets are, the whole trip is throttled by its tightest stretch. Finding that best-possible flow, and the bottleneck that caps it, is exactly the network-flow problem.
Start (middle school). Think of the network as water pipes. The source is where water enters, the sink is where it leaves, and every pipe has a width that limits how much can pass. You keep looking for any open route from source to sink, then push as much water through it as the narrowest pipe on that route allows. Do this again and again until no open route is left. Whatever total you have pushed by then is the maximum flow — the most the network can ever carry.
Build (high school). Give each edge a capacity $c(u,v)$ (its limit) and a current flow $f(u,v)$ (how much is using it now), with the rule $0\le f(u,v)\le c(u,v)$. A route from source $s$ to sink $t$ that still has room on every edge is an augmenting path, and the most you can add along it is the bottleneck — the smallest spare capacity on the path. For a single route $s\to a\to t$ with capacities $4$ and $3$, the bottleneck is $\min(4,3)=3$, so you send $3$ units. If a second route $s\to b\to t$ can carry $2$ more, the total value becomes $|f|=3+2=5$. The flow value is just the total leaving the source.
Deepen (AP / college). The clever bookkeeping is the residual graph: alongside each edge's leftover capacity $c_f(u,v)=c(u,v)-f(u,v)$, you keep a backward edge of capacity $f(u,v)$ that lets a later path cancel flow it now regrets — this “undo” is what makes the method reach a true optimum rather than getting stuck. Always picking the shortest augmenting path by breadth-first search (Edmonds-Karp) bounds the work at $O(VE^2)$, polynomial no matter the capacities. And the headline result, the max-flow min-cut theorem, says the maximum flow equals the smallest cut — the cheapest set of edges whose removal disconnects $s$ from $t$: $|f^\star|=\operatorname{cap}(S,T)$. When the search finally finds no augmenting path, the vertices still reachable from $s$ mark exactly that bottleneck cut.
Try this in the panel above. Drag the n slider and watch the Operations and Comparisons counters grow — a hands-on feel for how an algorithm's cost scales with problem size, the same scaling question that separates $O(E\cdot\text{maxFlow})$ from $O(VE^2)$. Switch the preset between Random, Sorted, and Reverse to see how the input changes the work, then press Reset to replay from the first step. (This panel runs SciSim's shared step-by-step tracer; a dedicated flow-network animation with live residual edges is on the way.)
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average / amortized complexity
Φ(S)
Potential function of data structure state S
α(n)
Inverse Ackermann function (~constant)
Step 1 — Residual Graph. For each edge (u,v) with capacity c and flow f: residual forward edge c−f (remaining capacity), residual backward edge f (cancellable flow). The residual graph enables flow to be 'undone' along previously chosen paths — essential for finding globally optimal flow.
Step 2 — Augmenting Path. A path from s to t in the residual graph with positive capacity on all edges. Bottleneck = minimum residual capacity along path. Send bottleneck units of flow along path. Repeat until no augmenting path exists.
Step 3 — Max-Flow Min-Cut Theorem. Max flow = Min cut (Ford-Fulkerson theorem). A cut (S,T) separates s∈S from t∈T. Cut capacity = sum of capacities of forward edges from S to T. When no augmenting path exists, the reachable vertices from s in residual graph define the min cut.
Step 4 — Ford-Fulkerson with DFS: O(E·maxFlow). If DFS is used to find augmenting paths: each augmentation takes O(E), and there can be O(maxFlow) augmentations. For irrational capacities: may not terminate. For integer capacities: always terminates.
Step 5 — Edmonds-Karp (BFS): O(VE²). Always find shortest augmenting path (fewest edges) using BFS. Number of augmentations: O(VE). Each augmentation: O(E) BFS. Total: O(VE²). Guaranteed polynomial regardless of capacity values.
The residual graph tracks remaining capacity for each direction. Forward edge: unused capacity. Backward edge: flow already sent (can be cancelled). Crucial insight: backward edges allow the algorithm to 'undo' earlier bad choices, enabling global optimality.
Why does BFS give a better bound than DFS for Edmonds-Karp? complex+
BFS finds shortest augmenting paths. Shortest path length can only increase or stay the same across augmentations (monotonicity lemma). Each edge can be the bottleneck of a shortest path at most V/2 times. Total augmentations: O(VE). Each augmentation O(E): total O(VE²).
How is bipartite matching reduced to max flow? applied+
Create source s, sink t. Edge from s to each left node (capacity 1). Edge from each right node to t (capacity 1). For each (left,right) pair in the bipartite graph: edge capacity 1. Max flow = maximum bipartite matching. O(E√V) with Hopcroft-Karp.
What is the Max-Flow Min-Cut theorem? concept+
Maximum flow from s to t equals minimum capacity of any s-t cut. Intuitively: you cannot push more flow than the bottleneck that separates s from t. Equivalently: when Ford-Fulkerson terminates, the set of vertices reachable from s in the residual graph defines the minimum cut.
Can Ford-Fulkerson fail to terminate? nonobv+
Yes — with irrational edge capacities, Ford-Fulkerson with DFS can augment by smaller and smaller amounts that converge to a value less than the true max flow (Ford-Fulkerson 1956 showed this). Edmonds-Karp (BFS) always terminates in O(VE²) regardless of capacities.
What is Dinic's algorithm? deep+
Dinic's algorithm: build layered graph (BFS level structure), find blocking flow in layered graph, repeat. Time: O(V²E). For unit-capacity graphs: O(E√V). For bipartite matching: O(E√V) — same as Hopcroft-Karp. Much faster than Edmonds-Karp O(VE²) in practice.
§5 — Misconceptions & Implementation Errors
Conceptual Misconceptions
✗ Ford-Fulkerson always terminates.
✓ Ford-Fulkerson with DFS may NOT terminate for irrational capacities. Edmonds-Karp (BFS) always terminates in O(VE²). For integer capacities, Ford-Fulkerson terminates in O(E·maxFlow).
✗ Max flow equals total capacity out of source.
✓ Max flow ≤ total capacity out of source, but may be less due to bottlenecks downstream. Max flow = minimum cut capacity, which can be much less than source's total outgoing capacity.
✓ Backward edges represent the option to CANCEL previously sent flow (equivalent to rerouting). They don't mean flow physically travels backwards in the network.
Implementation Errors
✗ Initializing residual capacity as a copy of forward capacity.
✓ Must initialize BOTH forward residual (= capacity) AND backward residual (= 0). Forgetting backward edges means flow can never be cancelled — algorithm may miss optimal flow.
✗ Using the same edge (u,v) and (v,u) without careful index tracking.
✓ Common bug: graph has both (u,v) and (v,u) edges. Must track each direction separately. Use edge index + reverse edge index. Mixing them corrupts residual updates.
✗ Stopping after first augmenting path instead of looping until no path exists.
✓ Must keep augmenting until NO augmenting path exists in the residual graph. Stopping early gives a valid but suboptimal (non-maximum) flow.