Max Flow / Min Cut Calculator
Compute the maximum flow and the minimum cut of a directed capacity network with Edmonds–Karp, naming the cut edges and checking the two numbers against each other.
Max Flow / Min Cut Calculator
Compute the maximum flow and the minimum cut of a directed capacity network with Edmonds–Karp, naming the cut edges and checking the two numbers against each other.
How this page computes
Capacities are written into a residual matrix. Each round finds a shortest augmenting path by breadth-first search, pushes its bottleneck, and updates the residual capacities in both directions.
When no path remains, a final breadth-first search over the residual graph marks the source side. The edges that cross from that side to the other are the cut, and their total is printed beside the flow.
The calculation runs entirely in this browser tab; nothing is uploaded.
The page pushes as much flow as the capacities allow from a source to a sink. On the sample network the answer is 13: A can pass 4 to T and B can pass 9, so the two throat capacities add up and the 10-unit feeds from S are not the limit.
It also prints the minimum cut — the cheapest set of edges whose removal disconnects the sink. Max-flow equals min-cut, so the two numbers printed side by side are a check on each other rather than two independent claims.
How to use Max Flow / Min Cut Calculator
Write one directed capacity per line as "S A 10", type the source and the sink, then press Run. Every capacity must be a whole number, because a capacity counts whole units.
The output gives the maximum flow, the cut capacity, which nodes stay on the source side, and which edges cross the cut. The augmenting-path count shows how many reroutes the search needed.
Edmonds–Karp, and why the cut proves the flow
The search finds a path from the source to the sink with spare capacity, pushes the largest flow that path allows, and repeats. Each push reduces the forward capacity and increases the backward capacity, which is what lets a later path undo an earlier choice.
When no path with spare capacity remains, the nodes still reachable from the source form the source side of a cut whose capacity equals the flow. That equality is the max-flow min-cut theorem, and the page computes both numbers separately so a disagreement would show.
What to Expect
Best for
- The largest throughput of a pipe, road or job-assignment network
- Finding the bottleneck edges of a flow network
- Checking a hand-traced augmenting path
Not ideal for
- Fractional capacities, which this page refuses rather than rounding
- Minimum-cost flow, where each unit also has a price
- Undirected networks with no stated direction
What this tool keeps
- Every capacity exactly as typed
What may need cleanup
- Nothing: the flow and the cut are final
Common errors
- A non-integer capacity is refused with the edge named
- A source equal to the sink is refused
- A negative capacity is refused
Example use cases
- Find the throughput of a two-pipe network
- Identify the cut edges that cap a flow
- Check that max-flow equals min-cut on a small graph
Sample input
S-A 10, S-B 10, A-T 4, B-T 9, A-B 2; source S, sink T
Sample output
maximum flow 13, minimum cut 13, cut edges A->T (4) and B->T (9)
Who this is for
- Students meeting network flow
- Engineers sizing a bottleneck
Frequently asked questions
Why is the answer 13 when the source feeds 20?
Because the two edges into the sink carry only 4 and 9. A flow is capped by its tightest cut, and the cut across A->T and B->T totals 13, so the extra 7 units have nowhere to go.
What does the backward capacity do?
It lets a later path cancel part of an earlier one. Without it the search could be trapped by a first choice, and the flow it found would be smaller than the true maximum.
Why must capacities be whole numbers?
A capacity is a count of units, so a fractional one would describe a different problem. The page refuses a decimal rather than rounding it, because a rounded capacity is a different network.
Build custom tools for your store
Join the SDK program to create useful ecommerce utilities for your store.