Max Flow Calculator

Pseudocode

Every maximum-flow algorithm in this family is the same loop: find a path from source to sink with spare capacity, push as much as it allows, repeat. The algorithms differ only in how they choose that path.

MaxFlow(graph, s, t):
    flow = 0
    build residual graph: cap(u,v) forward, 0 backward

    while there is an augmenting path P from s to t
          in the residual graph:
        bottleneck = min residual capacity along P
        for each edge (u, v) in P:
            residual[u][v] -= bottleneck
            residual[v][u] += bottleneck   // the undo edge
        flow += bottleneck

    return flow

// Ford-Fulkerson: find P by DFS (any path)
// Edmonds-Karp:   find P by BFS (shortest path)

The backward residual edge is the part that looks wrong and is in fact essential. It lets a later augmenting path cancel flow pushed earlier, which is how the algorithm escapes a bad early choice without backtracking. Without those undo edges the greedy loop gets stuck at a suboptimal flow.

Worked example, step by step

Run Edmonds-Karp on the standard example where a greedy first choice must later be undone.

Example graph: Directed capacities: S to A (10), S to B (10), A to B (2), A to T (4), B to T (9).

1. Augment 1. BFS finds S to A to T. The bottleneck is min(10, 4) = 4. Push 4. Total flow 4. Residual S-A drops to 6 and A-T to 0.
2. Augment 2. BFS finds S to B to T. The bottleneck is min(10, 9) = 9. Push 9. Total flow 13. Residual S-B drops to 1 and B-T to 0.
3. Augment 3. A-T and B-T are both saturated, so no direct route remains. BFS finds S to A to B to T? No: B-T is full. There is no augmenting path left.
4. Check the cut. Which edges are saturated? A-T at 4 and B-T at 9, total capacity 13. Removing them disconnects T from S, so this is a cut of capacity 13 and the flow of 13 matches it.
5. Why the undo edge would matter. Had the first augmenting path been S to A to B to T pushing 2, the A-B edge would be saturated in a way that blocks nothing here, but in graphs where the greedy path steals capacity a later path needs, the backward residual edge B to A lets that 2 units be pushed back and rerouted. The algorithm never has to backtrack explicitly.

Maximum flow is 13, and the minimum cut is the pair of edges A-T and B-T with total capacity 13. The two numbers being equal is not a coincidence: it is the max-flow min-cut theorem.

Complexity, and where it comes from

Time: O(V·E^2) Edmonds-Karp · Space: O(V + E)

Ford-Fulkerson with arbitrary path selection runs in O(E times maxflow), because each augmentation adds at least one unit but the path search costs O(E). That is pseudo-polynomial and genuinely bad: with capacities of a billion it can take a billion augmentations, and with irrational capacities it may not terminate at all. Edmonds-Karp fixes this by choosing the shortest augmenting path via BFS. The shortest-path distance from source to sink never decreases, and each edge can become the bottleneck at most V/2 times, bounding the number of augmentations at O(VE) and the total at O(V times E squared). Dinic groups augmentations into phases using a level graph and improves this to O(V squared times E), or O(E times sqrt(V)) on unit-capacity graphs.

When to use Maximum Flow, and when not to

The choice is mostly about capacity magnitudes and graph size.

Common pitfalls

• Omitting the backward residual edges. Without them the algorithm cannot undo an earlier bad augmentation and will terminate at a flow that is merely maximal, not maximum. This is the single most common max-flow bug and it produces plausible but too-small answers.
• Using DFS path selection with large capacities. Plain Ford-Fulkerson with DFS can need one augmentation per unit of flow on adversarial graphs. The classic example with capacities of a million and a bottleneck edge of one takes a million iterations. BFS makes the count independent of capacity values.
• Forgetting that flow conservation excludes source and sink. Every other node must have inflow equal to outflow. Validating conservation at the source or sink will always fail and is a common source of confusion when writing tests.
• Assuming the maximum flow is unique. The maximum flow value is unique; the flow assignment achieving it usually is not, and neither is the minimum cut when several have equal capacity. Tests must assert the value, not a particular edge-by-edge assignment.
• Modelling node capacities as edge capacities. If a node itself has a throughput limit, splitting it into an in-node and an out-node joined by an edge of that capacity is required. Applying the limit to incident edges gives a different, wrong problem.

Frequently asked questions

What is the maximum flow problem?

Given a directed graph where each edge has a capacity, plus a source and a sink, maximum flow asks for the greatest rate at which material can move from source to sink without exceeding any edge capacity and while conserving flow at every intermediate node. It models throughput in pipelines, networks, logistics and scheduling.

What is the max-flow min-cut theorem?

The value of the maximum flow from source to sink always equals the capacity of the minimum cut separating them. Intuitively, the flow cannot exceed any cut since everything must cross it, and when no augmenting path remains, the nodes reachable in the residual graph define a cut whose capacity exactly matches the flow.

What is the difference between Ford-Fulkerson and Edmonds-Karp?

They are the same augmenting-path method with a different path choice. Ford-Fulkerson leaves the choice unspecified, typically DFS, which makes the running time depend on capacity values and can be catastrophically slow. Edmonds-Karp always takes the shortest augmenting path via BFS, which bounds the work at O(V times E squared) regardless of capacities.

Why do max-flow algorithms need residual edges?

Because the algorithm is greedy and cannot look ahead. A backward residual edge represents the option to cancel flow already pushed along that edge, so a later augmenting path can reroute earlier decisions. That is what lets a purely forward-moving loop reach a true optimum without backtracking.

What is the time complexity of maximum flow?

Edmonds-Karp runs in O(V times E squared). Dinic improves it to O(V squared times E), and to O(E times the square root of V) on unit-capacity graphs, which is why it is preferred for bipartite matching. Plain Ford-Fulkerson is O(E times the maximum flow value), which is pseudo-polynomial rather than polynomial.