Maximum Flow Calculator

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:

• c01 is the capacity on edge 0 → 1
• c34 is 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.

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 = 5
• c13 = 15, c14 = 10
• c23 = 10, c24 = 10
• c34 = 10

One feasible sequence of augmentations (your algorithm may find the same value via different intermediate paths):

1. Send 10 along 0 → 1 → 4 (bottleneck min(10,10)=10)
2. Send 5 along 0 → 2 → 4 (bottleneck min(5,10)=5)
3. 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

Limitations & assumptions (important)

• Fixed size: the calculator supports exactly 5 nodes (0–4) with a full 5×5 matrix input.
• Directed edges: cij applies 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.

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.