An Edmonds-Karp Augmentation Sequence

The Edmonds–Karp Rule

Ford–Fulkerson augments a flow along a residual source-to-sink path. The choice of path can affect how the process proceeds. Edmonds–Karp makes that choice precise: at every stage, it uses breadth-first search (BFS) to find a residual path with the fewest edges. The point of this tutorial is to follow that rule through a complete augmentation sequence, including the residual capacities and the final cut certificate.

For an original edge \(uv\), the residual network has a forward residual arc \(u\to v\) of capacity \(c(u,v)-f(u,v)\), when this is positive, and a reverse residual arc \(v\to u\) of capacity \(f(u,v)\), when this is positive. Sending flow on a reverse residual arc cancels flow previously sent on the corresponding original edge. If a network has original edges in both directions, their residual arcs are kept distinct; the example below has no such pair.

BFS distance layers are sets \(L_i\) of vertices at residual distance \(i\) from \(s\), where distance is the minimum number of residual arcs in a path. Thus \(L_0=\{s\}\); each later layer consists of vertices first reached from the preceding layer. A path selected by BFS follows these layers in order. Ties between shortest paths may be resolved in any way.

Why the Updates Preserve Feasibility

Proof. A shortest path has no repeated vertex: if a vertex repeated, the portion between its two occurrences could be deleted to give a shorter path. On a forward residual arc, the update increases the original-edge flow by \(\Delta\), which is permitted because the residual capacity is at least \(\Delta\). On a reverse residual arc, it decreases the corresponding original-edge flow by \(\Delta\), which is permitted because that reverse residual capacity equals the current flow and is at least \(\Delta\). Thus all edge flows remain within their capacity bounds. At each internal path vertex the full amount \(\Delta\) enters and the same amount leaves, so conservation is preserved. At \(s\), net outflow increases by \(\Delta\), and at \(t\), net inflow increases by \(\Delta\). Therefore the updated flow is feasible and has value \(|f|+\Delta\). \(\square\)

Proof. BFS starts by assigning distance \(0\) to \(s\), then processes vertices in increasing order of their assigned distance, assigning a vertex's distance when it is first reached. We show by induction on \(i\) that every vertex at distance \(i\) from \(s\) is assigned distance \(i\). This holds for \(i=0\). If it holds through \(i\), every vertex at distance \(i+1\) has a neighbor at distance \(i\), so processing that neighbor reaches it with label at most \(i+1\). It cannot be reached with a smaller label, because that would give a path of fewer than \(i+1\) edges. Hence its assigned distance is \(i+1\). If \(t\) is reachable, following the predecessor links used to assign its label gives a path of that minimum length. If it is not reached, no residual path to \(t\) exists: the first unreached vertex on any proposed path would have been reached from its preceding vertex. \(\square\)

Tracing the Augmentations

Why the Final Cut Certifies the Answer

Proof. Since there is no residual \(s\)-\(t\) path, \(s\in S\) and \(t\notin S\). Every original edge from \(S\) to \(V\setminus S\) is saturated; otherwise its forward residual arc would reach a vertex outside \(S\). Every original edge from \(V\setminus S\) into \(S\) carries zero flow; otherwise its reverse residual arc would go from \(S\) to \(V\setminus S\), again reaching a vertex outside \(S\). Sum net outflow over all vertices in \(S\). Internal edges cancel, and flow conservation cancels the contributions of vertices other than \(s\), so the sum is the flow value. The crossing edges from \(S\) to \(V\setminus S\) contribute their full capacities, and edges in the opposite direction contribute zero. Hence the flow value equals the capacity of this cut. For any feasible flow and any cut separating \(s\) from \(t\), the same cancellation shows that its value is at most the cut capacity: each outward edge carries at most its capacity and each inward edge has nonnegative flow. Therefore no flow can exceed the current flow's value, proving maximality. \(\square\)

For the example, the edges leaving \(S=\{s,a,b,d\}\) are \(a\to c\), \(d\to c\), and \(d\to t\). Their capacities are \(12,7,4\), so the cut capacity is \(12+7+4=23\), equal to the flow value. This independently verifies the final answer: the flow is maximum and this cut is minimum.

Common Pitfall: Updating by the Wrong Amount

A path augmentation does not generally send one unit. On the third path here, the bottleneck is \(7\), so the full augmentation amount enters and leaves each internal vertex. For instance, at \(d\), \(7\) units enter on \(b\to d\) and \(7\) leave on \(d\to c\); conservation is preserved. A wrong update that subtracts only \(1\) from \(c\to t\) would give \(8-1=7\), but the correct residual capacity is \(8-7=1\). The bottleneck determines every forward subtraction and reverse addition on the path.

Edmonds–Karp is therefore more than a choice of a convenient path: BFS fixes the path length at each step, and the residual updates determine the next set of layers. Keeping those layers, bottlenecks, and reverse capacities explicit makes the sequence auditable. The final reachable set then turns the computation into a certificate rather than relying on the appearance of the flow alone.