18 Apr 2026Above you see a network of pipes and connectors through which a substance can flow, let's say water. Every pipe has a specific capacity, where no more water can flow than this maximum amount. The source is shown with a green border to the left, and the sink is marked in red at the right side. The problem is to find the maximum, total flow we can send from source to sink through the network, and which pipes to use in the process.
Mathematically this water network is just another weighted graph, with directed edges (pipes) between nodes, each having a capacity assigned to them. The nodes can handle as much flow as needed.
On the diagram above you can see a valid maximum flow solution for the network we had previously, with the chosen flow indicated by the blue lines. The general method used is called the Ford-Fulkerson method, more specifically we are using the Edmonds-Karp algorithm. For the remainder of this page we shall investigate how to find such a flow using these algorithms.
One proven property of network flow graphs is that there exists a minimum cut, separating source from sink, which has a sum of capacities equal to the maximum flow of the network. The diagram above shows such a minimum cut in yellow. Note that the yellow indicators split the network in two halves, so the entire flow from source to sink has to pass through the cut.
The Edmonds-Karp algorithm operates on a so-called residual graph, shown above for the same network as before. For every edge in the original graph we introduce two edges in the residual graph: a forward edge (darker grey) in the same direction as the original, and a reverse edge (lighter grey) in the opposite direction. The forward edge keeps track of how much more flow we could push along the original pipe, while the reverse edge lets the algorithm cancel flow it has already committed. Each augmenting path the algorithm finds is a path from source to sink through this residual graph. Note that the edges in the residual graph are weighted, but this is omitted from the diagram for simplicity. If an edge is absent, the weight at that edge is zero.
The animation above runs Edmonds-Karp on our network. Press play to watch each iteration: a breadth-first search (see graph search page) explores the residual graph from source to sink, painting traversed edges dark green. As soon as the sink is reached, the resulting shortest augmenting path flashes in violet. The algorithm then pushes as much flow along that path as the path's bottleneck allows, and the residual graph is redrawn — saturated forward edges disappear and new reverse edges open up where flow has been committed. The process repeats until no more source-to-sink paths exist in the residual graph; at that point the total flow pushed equals the maximum flow of the network.
Here we have another animated view of the Edmonds-Karp algorithm, where the shortest paths are the most basic item and are shown in light blue. It can then be seen whether edges in that path either add to the flow (green) or remove units of flow (red). By and by the overall network flow (dark blue) builds up. Note that by shortest path we are referring to the number of nodes along the path.
The Claude Opus LLM helped create this page. There are more algorithms and data structures to be found on the main page.
Please consider sharing this site on social media!