Edmonds-Karp, Capacity Scaling, Push-Relabel
What This Concept Is
Edmonds–Karp chooses an augmenting path with the fewest residual edges using BFS. This means shortest in hops, not smallest capacity sum or greatest bottleneck. It maintains the Ford–Fulkerson feasibility invariant while giving a polynomial augmentation bound independent of capacity magnitudes in the unit-cost model.
Why It Matters Here
A specified path rule turns a vague method into an analyzable algorithm. It also provides a useful distinction between arithmetic-operation bounds and the cost of large integer capacities. Faster flow methods are extensions, not interchangeable names for the reference implementation.
Concrete Examples
The BFS distances from source in residual graphs never decrease across augmentations. Every augmentation saturates at least one shortest-path residual edge u→v. To saturate that oriented edge again after it becomes available, some later path must use its reverse v→u. The level relationships force u's distance to increase by at least two before the same orientation can be critical again. Each oriented edge is critical O(V) times, giving O(VE) augmentations. An adjacency-list BFS scans O(E) relevant edge incidences, yielding the usual O(VE²) flow bound plus initialization and isolated-vertex bookkeeping.
The reference allocates V-sized arrays once and uses visitation generations, then scans them to return the final cut. This supports O(V+E+VE²) total operation accounting without clearing a large isolated-vertex array per search.
Common Confusion / Misconceptions
BFS follows positive residual edges, including cancellation arcs. Testing only positive original capacities is incorrect. Dinic builds level graphs and blocking flows; push–relabel maintains a preflow and heights. Neither is simply another BFS tie-breaking policy, and their bounds need their own invariants.
How To Use It
Retain bottleneck, predecessor residual arc IDs and final reachable vertices. Check each augmentation preserves capacities and conservation. Keep the complete flow/cut witness available. For performance experiments, vary topology, capacity bit width and source/sink location, and report actual augmentation counts.
Check Yourself
- What quantity does the BFS minimize?
- Why must a saturated orientation become farther away before being critical again?
- Where is the O(VE) augmentation bound used?
- What cost does exact large-integer arithmetic add beyond the unit-cost model?
Mini Drill or Application
Implement Lab D with BFS and paired residual arcs. Count augmentations on a small reassignment network, then change capacities by a large common factor: the numeric flow value changes without requiring that many unit augmentations. Explain why this differs from the generic value-based termination bound. See P18.
Read This Only If Stuck
Find Edmonds–Karp BFS levels and flow complexity in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.