Calculator
Example data table
This common network has a maximum flow of 23 from S to T.
| From | To | Capacity |
|---|---|---|
| S | A | 16 |
| S | B | 13 |
| A | B | 10 |
| B | A | 4 |
| A | C | 12 |
| B | D | 14 |
| C | B | 9 |
| D | C | 7 |
| C | T | 20 |
| D | T | 4 |
Use Load sample to populate the form automatically.
Formula used
The method repeatedly finds an augmenting path in the residual graph and pushes flow by the path bottleneck.
- Residual capacity: r(u,v) = c(u,v) − f(u,v)
- Path bottleneck: Δ = min r(u,v) along the chosen path
- Augment: f(u,v) ← f(u,v) + Δ and update reverse residual
This calculator uses a breadth-first search variant (Edmonds–Karp) to pick augmenting paths, producing a reliable maximum flow.
How to use this calculator
- Set the number of nodes and choose directed or undirected.
- Enter source and sink node numbers within 1..n.
- Add edges with positive capacities in the table.
- Optionally provide node labels to improve readability.
- Click Compute maximum flow to see results above the form.
- Use the download buttons to export CSV or PDF reports.
FAQs
1) What does maximum flow represent?
It is the largest transferable amount from source to sink while respecting edge capacity limits. It models routing, throughput, and allocation problems in networks.
2) Why do you show an augmenting path log?
The log lists each found path, its bottleneck, and the running total. It helps you debug inputs and understand how the final flow was built.
3) What is a residual graph?
It is a graph showing remaining capacity on each edge after current flow. Residual edges allow both pushing more flow forward and canceling flow backward.
4) How is the minimum cut related to max flow?
At optimum, the max flow value equals the capacity of a minimum s–t cut. The cut edges listed separate reachable nodes from unreachable nodes in the final residual graph.
5) Can I use non-integer capacities?
Yes. The solver accepts decimal capacities and outputs rounded values. For best stability, keep capacities within a reasonable numeric range.
6) What happens if I enter repeated edges?
Repeated edges between the same ordered pair are summed into one capacity. This is useful when multiple parallel links exist in your network.
7) Does undirected mode change the algorithm?
Undirected mode adds the same capacity in both directions, effectively treating each edge as two directed edges. Flow and cuts are then computed on that directed representation.
8) Why might the maximum flow be zero?
If there is no directed path from source to sink with positive capacities, no flow can be sent. Check connectivity, direction, and that capacities are greater than zero.