Maximum Flow Calculator
The maximum flow problem (what this calculator does)
The maximum flow problem asks: given a directed network with capacities on each edge, how much “stuff” (water, traffic, data, money, etc.) can be sent from a source node s to a sink node t without exceeding any edge capacity? This calculator solves that problem for a fixed-size network of 5 nodes labeled 0–4, using the Edmonds–Karp algorithm (a specific, polynomial-time variant of the Ford–Fulkerson method).
You provide a 5×5 capacity matrix c(i,j), where each entry represents the capacity of the directed edge from node i to node j. A capacity of 0 means “no usable edge” (or an edge with zero capacity). The calculator then finds the maximum feasible flow value from the chosen source to the chosen sink.
Inputs: capacity matrix, source, and sink
Capacity entries c(i,j)
Each input labeled cij corresponds to capacity from node i to node j. For example:
c01is the capacity on edge 0 → 1c34is the capacity on edge 3 → 4
Directed vs. undirected: this is a directed-network calculator. To model an undirected edge between i and j with capacity C, enter cij = C and cji = C.
Source and sink
Choose:
- source s (0–4): the node where flow originates
- sink t (0–4): the node where flow is collected
If s = t, the maximum flow value is typically 0 (there is no need to send flow across edges to reach the sink).
Core constraints and formulas
A flow assigns a value f(u,v) to each directed edge (u,v). It must satisfy:
- Capacity constraints: 0 ≤ f(u,v) ≤ c(u,v)
- Flow conservation at every intermediate node v (all nodes except s and t): total inflow equals total outflow.
The value of the flow is the total amount leaving the source (equivalently, the total amount entering the sink in a feasible flow).
Math notation (MathML)
The standard definitions can be written as:
In this calculator, V has exactly 5 nodes (0–4), and the capacities c(u,v) are your inputs.
Algorithm used: Edmonds–Karp (Ford–Fulkerson variant)
Ford–Fulkerson increases flow by repeatedly finding an augmenting path from s to t in the residual network—a graph that tracks how much additional flow can be pushed on each edge (and how much can be “undone” via reverse edges). The Edmonds–Karp variant always chooses an augmenting path found by BFS (fewest edges), which guarantees polynomial runtime.
Key idea: the amount you can add along a path is limited by its bottleneck (the minimum residual capacity on the path). After pushing that amount, residual capacities update: forward edges decrease; reverse edges increase.
Interpreting the result
The main output is the maximum flow value: the greatest feasible amount that can be sent from your chosen source to sink. Useful ways to interpret it:
- If it is 0, then there is no directed path with positive capacity from source to sink (or source equals sink).
- If it is positive but smaller than you expected, check for bottlenecks: a small-capacity edge (or a small cut of edges) may limit total throughput.
- By the max-flow min-cut theorem, the max flow value equals the capacity of a minimum s–t cut. Informally, there is a “thin boundary” of edges whose total capacity exactly limits the flow.
Worked example (5×5 matrix)
Use source s = 0 and sink t = 4. Enter these nonzero capacities (all unspecified entries are 0):
c01 = 10,c02 = 5c13 = 15,c14 = 10c23 = 10,c24 = 10c34 = 10
One feasible sequence of augmentations (your algorithm may find the same value via different intermediate paths):
- Send 10 along 0 → 1 → 4 (bottleneck min(10,10)=10)
- Send 5 along 0 → 2 → 4 (bottleneck min(5,10)=5)
- Send 5 along 0 → 1 → 3 → 4 (bottleneck min(remaining 0→1 is 0? depends on prior choice; alternatively 0→1→3→4 first; the final maximum remains the same)
The computed maximum flow for this network is 20.
Takeaway: even though there may be many paths from 0 to 4, the combined capacities leaving node 0 (10+5=15) and other downstream constraints determine the true maximum. In this example, additional routing through node 3 helps achieve the final total.
Comparison: common max-flow algorithms
| Algorithm | Main idea | Typical complexity (conceptual) | When it’s a good fit |
|---|---|---|---|
| Ford–Fulkerson | Repeatedly augment along any s–t path in residual graph | Depends on path choice; can be slow with irrational capacities | Small graphs; educational use |
| Edmonds–Karp | Ford–Fulkerson + BFS for shortest augmenting paths | Polynomial; O(V·E²) | Reliable, simple, great for small/medium graphs |
| Dinic | Blocking flows in level graphs | Often faster in practice; strong bounds on many cases | Larger graphs where performance matters |
| Push–relabel | Local pushes with node “heights” and excess flow | Very fast on many dense graphs | Industrial-scale max-flow / dense networks |
Limitations & assumptions (important)
- Fixed size: the calculator supports exactly 5 nodes (0–4) with a full 5×5 matrix input.
- Directed edges:
cijapplies to i → j only. Use both directions to mimic an undirected link. - Nonnegative capacities: capacities should be ≥ 0. Negative values do not represent valid max-flow capacities.
- Diagonal entries: values like
c00,c11, etc. represent self-loops. In most flow models, self-loops are ignored and do not help increase s–t flow; you can leave them as 0. - Decimals: the inputs allow decimals; the underlying method assumes standard real-valued capacities. (If you need integer-only behavior, enter integers.)
- Feasibility model: only capacity constraints and flow conservation are enforced—there are no costs, demands, or lower bounds.