Max-Flow Min-Cut Calculator

Augmenting paths, residual graph and the minimum cut.

  • Path-by-path trace
  • Minimum cut shown
  • Residual graph
A small rounded clay table holding a network of soft round knots joined by pipes of different widths, with a few loose beads resting along the pipes in soft daylight.

The guide

Why a flow can be improved by sending some of it back, and why one cut proves the flow is largest

A shortest-path search finds the largest flow through a capacity network only if it may undo earlier choices. The last residual graph then hands over a cut that proves nothing larger exists.

  • 3, 3, 5 and 6 edges in the four augmenting paths of the nine arcs, never decreasing
  • 4 instead of 5 flow of the same network when reverse residual edges are left out
  • 7 instead of 5 cut capacity when the edge D to E running back is counted too
  • 1 of 32 cuts of the nine arcs that reach the minimum, so it is unique
  • 277 of 277 seeded random networks where flow, cut and a second algorithm agree
Read the full guide Fold the guide 7 min · 15 sources

Picture a network of pipes carrying water from a reservoir to a city. Every pipe has a most it can carry, and the question is how much can reach the city at once. Wikipedia’s page on the max-flow min-cut theorem uses exactly this picture, and it adds the answer’s strange twin: the amount is limited by the smallest total capacity of any set of pipes that would cut the reservoir off.

The problem is older than the pipes. Wikipedia records that T. E. Harris and F. S. Ross formulated it in 1954 as a simplified model of Soviet railway traffic, and that Lester Ford and Delbert Fulkerson published the first known algorithm in 1955. Their question was about trains and cities, but the arithmetic is the same. NIST’s dictionary of algorithms states the task in one line: find the maximum flow between two vertices of a directed graph.

Why a flow sometimes has to go backwards

Take the nine arcs that the Edmonds-Karp page uses: A to B with capacity 3, A to D 3, B to C 4, C to D 1, C to E 2, D to E 2, D to F 6, E to G 1 and F to G 9. The source is A and the sink is G. The method looks for a path with room left on every edge, sends as much as the tightest edge allows, and repeats.

The first path, A, D, E, G, is limited by the one-unit edge E to G, so it carries 1. The second, A, D, F, G, carries 2 and fills A to D. The third, A, B, C, D, F, G, carries 1. That is a total of 4, and every route that uses only the original edges is blocked. A beginner might stop here.

The fourth path does not exist in the original network. It runs A, B, C, E, D, F, G, and the step from E to D goes against the arrow. The Ford-Fulkerson page explains why that is allowed. The residual capacity of an edge is its capacity minus its flow, and when flow f from u to v is positive, a flow from v back to u becomes possible in the residual network, with room equal to f.

In plain terms, the algorithm is allowed to change its mind. Path one pushed 1 unit along D to E. Sending 1 unit from E to D cancels it, so the unit that used to travel D, E, G now arrives at G the same way, while the unit that arrived at D from C goes on to F instead. The total becomes 5, and D to E ends with no flow at all.

Leave the reverse edges out and the same network stops with a flow of 4 instead of 5. That is the commonest error in hand-written solvers, and it is easy to miss because a flow of 4 looks like an honest answer. The Flow network page states the rule that catches it: a network is at maximum flow if and only if no augmenting path exists in the residual network, and that residual network includes the reverse edges.

Why the shortest path rule bounds the work

The Ford-Fulkerson page calls its approach a method rather than an algorithm, because it does not say which augmenting path to take. That freedom is dangerous. The page gives a four-node network where unlucky choices send a single unit at a time and need 2,000 steps to reach a flow of 2,000, while breadth-first search would need two. With integer capacities the running time is bounded by the number of edges times the flow value, so a large flow means a long run.

Worse, with irrational capacities and bad choices the method may never end. The page’s example uses a capacity of (the square root of 5, minus 1) divided by 2, and the flow it builds might not even converge to the maximum.

Edmonds and Karp fixed this by choosing the shortest path, measured in edges. Breadth-first search finds it: NIST’s dictionary describes the search as one that considers the neighbours of a vertex before going deeper, usually with a queue. Wikipedia adds that its time is linear in the number of vertices plus edges.

The Edmonds-Karp page gives the proof outline in three moves. The distance from the source to any other node never shrinks after an augmentation, so the path lengths found never decrease; in the nine arcs they are 3, 3, 5 and 6 edges. Each edge can be the saturated bottleneck only a limited number of times, at most half the number of nodes. And each search costs time proportional to the number of edges. Together that gives a running time on the order of the nodes times the edges squared, no matter how large the capacities are.

The Dinic page tells the history. Yefim Dinitz published the idea in 1970 and Edmonds and Karp found it independently in 1972. For about ten years it had been unknown whether the method could be made to stop in polynomial time, and both results settled it. Dinitz’s version adds level graphs and blocking flows and lowers the bound to the square of the nodes times the edges.

Why a cut limits every flow

A cut splits the nodes into two groups, with the source in one and the sink in the other. Its capacity is the sum of the capacities of the edges that run from the source group to the sink group. Edges that run the other way are not counted, and this is the rule most often broken: they carry nothing toward the sink.

Every flow must cross every cut, so no flow can exceed the capacity of any cut. That alone gives an upper bound. The theorem says the bound is reached: the largest flow equals the smallest cut capacity, and Wikipedia notes that it is a special case of linear programming duality.

The nine arcs have 32 cuts, because each of the five nodes other than A and G can sit on either side. Their capacities run from 5 up to 18. Only 1 of 32 cuts reaches 5, the one with A, B, C and E on the source side. Its edges are A to D with 3, C to D with 1 and E to G with 1. The edge D to E runs back across it and is not counted.

Count it anyway and the same cut reads 7 instead of 5. That is the second common mistake, and it is easy to make: 3 plus 1 plus 1 plus 2 is a sum that looks as honest as the right one. The smallest cut under that wrong rule is 6, a different cut altogether.

Reading the proof off the last residual graph

When no augmenting path is left, the set of nodes the source can still reach in the residual graph is the source side of a cut. The Ford-Fulkerson page states that this cut has capacity equal to the flow, and that it is also an upper bound for every flow, so the flow is maximal.

Why does it work? Every edge leaving the reachable set must be full, or its head would be reachable too. Every edge entering the reachable set must be empty, or the reverse residual edge would let the source reach its tail. A full outgoing edge adds its whole capacity to the flow across the cut and an empty incoming edge takes nothing back, so the flow equals the cut capacity. In the nine arcs, D to E ends at zero.

The reachable set is also the smallest possible source side among minimum cuts, which follows from the same argument, and the calculator confirms it by brute force on its test networks. When several cuts tie, the one the method reports has the fewest nodes on the source side. Two edges of capacity 2 from the source to two nodes, each with a 2-edge to the sink, give four cuts that all reach capacity 4.

The Menger page shows the same idea at work in a smaller setting. It says that the size of a minimum cut equals the greatest number of disjoint paths between two vertices, and that the max-flow min-cut theorem generalises it with weights.

What it can and cannot do

The Maximum flow problem page lists uses beyond pipes and trains, including bipartite matching and baseball elimination. It also states the integral flow theorem: if every capacity is a whole number, some maximum flow puts a whole number on every edge. That is why this calculator can hold decimals as whole numbers of a thousandth and stay exact.

Exactness is the reason for that choice. The Python documentation explains that decimal fractions such as 0.1 cannot be represented exactly as binary floating point numbers, so a stored value is only an approximation of what was typed. Whole numbers of a thousandth avoid the problem. The same documentation describes the fractions module for rational arithmetic, used to check the decimal examples, and the itertools module, whose combinations function lists every subset of the other nodes that makes up a cut.

The checks were run on seeded random networks of 3 to 8 nodes with capacities 1 to 9. In 277 of 277 networks four routes gave the same number: the shortest-path flow, a second algorithm, the smallest of all cuts, and the cut read from the residual graph. The page does its work in a module worker, as the MDN page on Web Workers describes, so a large edit never freezes the tab, and it formats numbers with Intl.NumberFormat.

The limits are real. The method has one source and one sink; Wikipedia’s Flow network page describes the usual repair of adding a super source and super sink. It does not handle lower bounds on edges, costs, or capacities that change over time. The page also lists 14 nodes and 60 edges as its cap, so it is a way to see and check the idea, not a planning system.

Sources

Every source consulted for this guide. Links checked November 11, 2026.

  1. Edmonds-Karp algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  2. Ford-Fulkerson algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  3. Max-flow min-cut theorem - Wikipedia Wikipedia (CC BY-SA 4.0)
  4. Flow network - Wikipedia Wikipedia (CC BY-SA 4.0)
  5. Maximum flow problem - Wikipedia Wikipedia (CC BY-SA 4.0)
  6. Dinic's algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  7. Menger's theorem - Wikipedia Wikipedia (CC BY-SA 4.0)
  8. Breadth-first search - Wikipedia Wikipedia (CC BY-SA 4.0)
  9. maximum-flow problem NIST Dictionary of Algorithms and Data Structures
  10. breadth-first search NIST Dictionary of Algorithms and Data Structures
  11. Web Workers API - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  12. Intl.NumberFormat - JavaScript | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  13. fractions - Rational numbers - Python 3.13 documentation Python Software Foundation (PSF License Version 2)
  14. itertools - Functions creating iterators for efficient looping - Python 3.13 documentation Python Software Foundation (PSF License Version 2)
  15. Floating-Point Arithmetic: Issues and Limitations - Python 3.13 documentation Python Software Foundation (PSF License Version 2)