Max Flow Calculator

What Is the Maximum Flow Problem?

The maximum flow problem is one of the most fundamental problems in combinatorial optimization and network theory. Given a directed graph where each edge has a non-negative capacity — the maximum amount of flow it can carry — the goal is to determine the greatest total flow that can be routed from a designated source node to a designated sink node, subject to two constraints: flow on each edge must not exceed its capacity, and flow must be conserved at every intermediate node (inflow equals outflow).

Flow networks appear throughout science and engineering. Water flowing through pipes, data packets through Internet routers, goods through supply chains, cars through road networks — all can be modeled as flow networks. The maximum flow then represents the network's throughput capacity.

Ford-Fulkerson Method

The Ford-Fulkerson method, introduced by L.R. Ford Jr. and D.R. Fulkerson in 1956, is the foundational approach for solving max flow problems. The method maintains a residual graph — a modified version of the original graph that represents remaining capacity. At each step it finds an augmenting path from source to sink in the residual graph and pushes as much flow as possible along that path. When no augmenting path exists, the algorithm terminates with the optimal solution.

Ford-Fulkerson is a method, not a specific algorithm, because it does not specify how to find augmenting paths. Different search strategies yield different algorithms with different complexity guarantees. With DFS, the number of iterations can be exponential on graphs with irrational capacities. With BFS, the Edmonds-Karp algorithm achieves polynomial time.

Edmonds-Karp Algorithm

The Edmonds-Karp algorithm, independently discovered by Jack Edmonds and Richard Karp in 1972, implements Ford-Fulkerson using breadth-first search (BFS) to find the shortest augmenting path (fewest edges) at each iteration. This simple modification provides a crucial complexity guarantee:

• Each BFS finds the shortest path in O(V + E) time.
• The total number of augmenting path iterations is bounded by O(VE).
• Overall time complexity: O(VE²) where V = vertices, E = edges.

This polynomial bound makes Edmonds-Karp highly practical. For example, a network with 50 nodes and 200 edges would need at most 50 × 200 = 10,000 BFS iterations — entirely feasible.

Residual Graph and Augmenting Paths

A residual graph captures how much additional flow can be sent along each edge. For every original edge (u → v) with capacity c and current flow f, the residual graph has:

• A forward edge (u → v) with residual capacity c − f (remaining space).
• A backward edge (v → u) with residual capacity f (allows canceling flow).

The backward edges are the key insight: they let the algorithm "undo" suboptimal routing decisions found in earlier iterations, effectively allowing it to reroute flow through better paths.

An augmenting path is any path from source to sink in the residual graph where all edges have positive residual capacity. The bottleneck of the path — the minimum residual capacity along it — determines how much additional flow can be pushed.

Max-Flow Min-Cut Theorem

The Max-Flow Min-Cut theorem is a landmark result stating that for any flow network, the maximum flow equals the minimum cut capacity. A cut is a partition of the nodes into two sets S (containing the source) and T (containing the sink); its capacity is the sum of capacities of edges going from S to T. The minimum cut is the cut with smallest total capacity.

This duality has profound implications: finding the max flow simultaneously reveals the network's bottleneck (the min cut). In a transportation network, the min cut identifies the most congested set of links that limits overall throughput. In bipartite matching, it identifies the maximum matching via König's theorem.

Applications

Max flow is one of the most widely applied algorithms in computer science and operations research:

• Internet routing: Maximizing data throughput between network nodes.
• Bipartite matching: Job scheduling, assignment problems, and stable matching reduce to max flow.
• Image segmentation: Graph cut methods (Boykov-Kolmogorov) use min cuts to separate foreground from background.
• Supply chain optimization: Routing goods through distribution networks to maximize throughput.
• Project scheduling: Resource-constrained critical path analysis via network flow.
• Sports elimination: Determining whether a team can still win a league uses max flow.
• Network reliability: Identifying critical links whose removal most reduces network capacity.