This simulation runs Edmonds–Karp, the breadth-first-search variant of Ford–Fulkerson, on a directed capacitated network to find the maximum flow from a source s to a sink t. Each click of Step performs one full iteration: BFS searches the residual graph for the shortest augmenting path, pushes flow equal to that path's bottleneck capacity, and updates the residual capacities (including the reverse edges that let the algorithm "undo" flow later). When BFS can no longer reach the sink, the algorithm halts and reveals the minimum cut — by the max-flow min-cut theorem, its capacity always equals the maximum flow found.
A live residual graph for one of five preset networks (or a randomly generated layered DAG). Blue edges are carrying flow, red edges are saturated (flow equals capacity), and green marks the current augmenting path found by BFS. Once no augmenting path remains, gold edges mark the min-cut and node fill shows which side of the cut — reachable from s (green) or not (orange) — each node ends up on.
Choose a network from the Preset network dropdown, then press Step to run one Edmonds–Karp iteration at a time, or Auto-run to let it play automatically at a rate set by the Animation speed slider (Pause stops it, Reset reloads the chosen preset from scratch). Watch the live Statistics panel for the current flow value, the min-cut capacity once found, the number of augmenting paths pushed so far, and how many BFS iterations have run.
Because Edmonds–Karp always augments along a shortest path (fewest edges) in the residual graph, it is guaranteed to terminate in at most O(V·E) augmentations regardless of edge capacities — unlike the plain Ford–Fulkerson method, which can be forced into an enormous or even infinite number of tiny augmentations on adversarial integer-weighted graphs.
It runs Edmonds–Karp: repeated breadth-first search over the residual graph to find the shortest available augmenting path from source to sink, then pushing flow equal to that path's bottleneck (minimum residual capacity) along every edge on the path. This is a specific, well-behaved implementation of the general Ford–Fulkerson method.
The residual graph tracks how much additional capacity remains on each edge after flow has been pushed. Every original edge gets a paired reverse edge with capacity equal to the flow already sent; pushing flow along that reverse edge effectively cancels some of the forward flow. These reverse edges are what let the algorithm correct an earlier, suboptimal routing choice in a later iteration.
When BFS from the source can no longer reach the sink in the residual graph, the simulation marks every node still reachable from the source as the "S-side" and every other node as the "T-side." The min cut consists of the original edges that go from an S-side node to a T-side node, and summing their capacities gives the cut capacity — which the max-flow min-cut theorem guarantees equals the maximum flow value.
Current flow value is the total flow pushed from source to sink so far; Min-cut capacity appears only once the algorithm finishes and equals the final max flow; Augmenting paths counts how many successful BFS paths have carried flow; BFS iterations counts every search performed, including the final one that fails to reach the sink and triggers termination.
Because Edmonds–Karp always picks the shortest augmenting path by number of edges, it can be proven that the distance from source to any node never decreases across iterations, which bounds the total number of augmentations by O(V·E). Plain Ford–Fulkerson has no such rule for choosing a path, so on certain graphs with poorly chosen paths it can take vastly more iterations, or fail to terminate at all with irrational capacities.