The Maximum Flow Problem

Network flow theory studies how a commodity like water, traffic, or data moves through a system of directed edges. Each edge carries at most a certain amount, its capacity. Given a designated source where flow originates and a sink where it is consumed, the maximum flow problem asks for the greatest possible rate from source to sink without violating capacities. Mathematically, we model the network as a directed graph $G=\left(V,,,E\right)$ with capacity function $c:E\to R^+$. A flow assigns a value $f(u,v)$ to each edge satisfying two principles:

$$

$(1)$	$0\le f(u,v)\le c(u,v)$
$(2)$	$\sum _{\mathrm{u:(u,v)\in E}}^{}f(u,v)=\sum _{\mathrm{w:(v,w)\in E}}^{}f(v,w)$

Condition (1) enforces capacity limits, while condition (2) expresses conservation at intermediate vertices: flow in equals flow out. The value of the flow is the net amount leaving the source, and the goal is to maximize this quantity. Applications range from routing internet packets to scheduling airlines and even solving bipartite matching through flow formulation.

Ford–Fulkerson and the Residual Network

Our calculator implements the Edmonds–Karp variant of the Ford–Fulkerson method. Starting with zero flow, the algorithm repeatedly searches for an augmenting path from source to sink in the residual network. The residual capacity of an edge is how much additional flow it can support; initially this equals the original capacity. After sending flow along a path, we decrease forward residual capacities and increase reverse capacities, allowing the algorithm to cancel previous decisions if a better route emerges.

Edmonds–Karp uses breadth-first search to find the shortest augmenting path in terms of edge count. This strategy guarantees polynomial time: at most $O\left(VE^2\right)$. For our small 5×5 network the complexity is insignificant, but the method mirrors how large industrial solvers operate.

Step-by-Step Example

Suppose we have a simple network with source 0, sink 4, and the following capacity matrix:

	0	1	2	3	4
0	0	10	5	0	0
1	0	0	15	10	0
2	0	0	0	10	10
3	0	0	0	0	10
4	0	0	0	0	0

One augmenting path is 0→1→3→4 with bottleneck 10, giving a flow of 10 units. Residual capacities adjust accordingly. Another path 0→2→4 adds 5 units, and finally 0→1→2→4 contributes 5 more, reaching a maximum flow of 20. The minimum cut separating the source and sink also has capacity 20, verifying the max-flow min-cut theorem.

Why Max Flow Matters

Beyond transportation and communication networks, max flow forms a backbone for many algorithms. Bipartite matching, project selection, image segmentation, and baseball elimination all reduce to flow computations. In linear programming, max flow is a special case with a totally unimodular constraint matrix, ensuring integer solutions without explicit integrality constraints. The problem also has theoretical implications in graph theory, tying into cuts, connectivity, and planar duality.

Flow algorithms highlight the power of algorithmic thinking. By interpreting capacities as resources and paths as choices, the method finds globally optimal distributions through local updates. The residual network encapsulates unused potential and the ability to reroute, a concept with analogs in electrical circuits and fluid dynamics.

Using This Calculator

Enter capacities for each ordered pair of nodes in the 5×5 matrix. A zero indicates no direct edge. Specify the source and sink indices between 0 and 4. Upon submission, the script constructs the capacity matrix and repeatedly runs a breadth-first search to locate augmenting paths. After each path, it updates residual capacities and accumulates the flow value. The process halts when no further paths exist, and the final maximum flow is displayed. All computations occur client-side with plain JavaScript, so no data leaves your browser.

Experiment with different networks to see how bottlenecks limit throughput. Try adding high capacity edges that still fail to increase flow because of a single low-capacity link – this illustrates the concept of a cut. The calculator resets the residual network each run, making it easy to modify capacities and observe changes.

Further Exploration

Max flow can be extended in many directions. The minimum cost flow problem adds costs to edges and seeks the cheapest way to send a specified amount of flow. Multi-commodity flow allows several independent flows through the same network. Dynamic flows incorporate time, modeling traffic that moves over intervals. While our calculator handles only a tiny static network, understanding the core algorithm lays groundwork for these advanced topics.

Historically, Ford and Fulkerson introduced their augmenting path method in the 1950s while studying railway logistics. Their work led to the famous theorem equating maximum flow with minimum cut capacity. Edmonds and Karp later refined the method to ensure polynomial runtime, a hallmark in the development of efficient algorithms. Today network flow remains a vibrant area connecting combinatorial optimization, operations research, and theoretical computer science.

By experimenting with this tool, you can build intuition for flows, cuts, and algorithms. Try constructing a network where the direct edge from source to sink is not part of any maximum flow because alternative routes provide more capacity. Observe how augmenting paths may traverse edges in reverse as the residual network evolves, undoing earlier choices to accommodate better ones.

Whether you are tackling homework, preparing for contests, or designing real systems, mastering max flow opens doors to a wealth of applications. The simplicity of the Edmonds–Karp algorithm belies its power: with just loops and arrays, you can solve problems that underpin internet routing, supply chains, and image processing. This calculator invites you to engage with those ideas hands-on.