The maximum flow problem
A flow network has a source, a sink, and edges with capacities. We want to send as much flow as possible from source to sink without exceeding any capacity and keeping flow balanced at every other node.
Augmenting paths
The Ford Fulkerson method repeatedly finds a path from source to sink with spare capacity, called an augmenting path, and pushes flow along it. To allow corrections it also tracks residual edges that let flow be pushed back. Edmonds Karp is the version that always picks the shortest such path by edge count.
- Search for an augmenting path using breadth first search.
- Push flow equal to the smallest spare capacity on that path.
- Update residual capacities and repeat until no path remains.
Why the shortest path choice matters
Choosing the shortest augmenting path each time keeps the algorithm from making tiny inefficient pushes. It guarantees termination in a number of steps bounded by the graph size, independent of the capacity values, which raw Ford Fulkerson cannot promise.
Key idea
Repeatedly push flow along the shortest augmenting path found by breadth first search, updating residuals, until none remains.