Max flow, min cut, and the Ford-Fulkerson algorithm
Push water through a network of pipes, each with its own limit. How much can reach the sink, and where is the bottleneck?
Pick a network, click an edge, and raise or lower its flow. Watch the capacity and conservation checks flag any rule you break.
Click an edge to select it, then use controls below to adjust flow
Network flow models the transportation of commodities through a network from a source to a sink. Each edge has a capacity limit, and we want to maximize the total flow while respecting these constraints.
A flow network is a directed graph where each edge has a capacity. Flow travels from a source to a sink, obeying capacity constraints and conservation laws. A valid flow must satisfy two constraints at every node: capacity (flow cannot exceed edge capacity) and conservation (flow in equals flow out at intermediate nodes).
Press Step to push flow along one augmenting path at a time, or Run Algorithm to watch it finish. Watch the current flow climb with each path.
The Ford-Fulkerson algorithm finds maximum flow by repeatedly discovering augmenting paths from source to sink in the residual graph and pushing flow along them. This implementation uses BFS (Edmonds-Karp variant), guaranteeing O(VE^2) time. The residual graph includes backward edges that allow the algorithm to “undo” previous flow decisions, ensuring it always converges to the global optimum.
Press Find Max Flow & Min Cut, then compare the max flow with the total capacity of the highlighted cut edges.
The max-flow min-cut theorem states that the maximum flow from source to sink equals the minimum capacity of any cut separating them. A cut partitions vertices into two sets, with the source in one and the sink in the other. This duality between flow and cuts is a cornerstone of combinatorial optimization — the bottleneck of any network is determined by its weakest separating boundary.
Click worker-job pairs to switch qualifications on or off, then press Find Maximum Matching. Green edges show the matched pairs.
Green edges = matched pairs in optimal solution
Maximum bipartite matching reduces to a max-flow problem: connect a source to one partition, the other partition to a sink, and set all capacities to 1. The maximum flow equals the size of the largest matching. Reducing matching to flow demonstrates the power of network flow as a general framework — many optimization problems on bipartite structures can be solved this way.
Spot a mistake or have an idea?