cf.completefrontend
GRAPHS · ADVANCED

Maximum flow (Edmonds-Karp)

Find the most that can flow from a source to a sink through edges with capacity limits, by repeatedly pushing flow along the shortest path that still has room.

Time O(n * e) rounds of BFSSpace O(n²)2 practice problemsStep-through picture

The idea

Picture a network of pipes, each with a limit on how much water it can carry per second, called its capacity. Water enters at a node called the source and leaves at a node called the sink. The maximum flow is the most water per second that can get from source to sink without any pipe going over its limit.

The Ford-Fulkerson idea: find any path from source to sink where every pipe still has spare room (an augmenting path), push as much as the tightest pipe on it allows (the bottleneck), and repeat until no such path exists. Edmonds-Karp is the version that finds each path with BFS, which keeps the number of rounds small.

The clever part is undo edges. When you push flow along a → b, you also add that much spare room on b → a. A later path may use b → a to cancel some earlier flow and send it a better way. Without undo edges, an early bad choice could block the true maximum.

An everyday example

Moving people through a building with narrow doors

A crowd must move from the lobby to the exit through rooms joined by doors, and each door only lets a certain number of people through per minute. You keep finding a route with spare room at every door and send as many people as the narrowest door allows. Sometimes you realize a group should have gone another way, so you redirect them, freeing up a door for a new route. When no route has spare room left, you've found the most people per minute the building can move.

How the example maps to the code
In the exampleIn the code
A door's limitcap[from][to]
A route with spare room at every doorA BFS path where every cap is above 0
The narrowest door on the routebottleneck
Redirecting people who took a doorAdding to the undo edge cap[v][parent[v]]
People moved per minuteflow

From the slow way to maximum flow (edmonds-karp)

  1. Start with the obvious greedy way: find any path from source to sink where every edge has room, push as much as the tightest edge allows, and repeat until no such path exists. It sounds right, but an early path can take room that a better plan needed. In the trace's graph, this greedy method stops at 4 when the true maximum is 5.
  2. The fix is to let later paths undo earlier choices. When b units are pushed along a → b, add b units of room to the opposite direction, b → a. A later path that uses b → a is really saying "send less along a → b and reroute it". With these undo edges, getting stuck finally means the flow can't grow at all.
  3. Which path should each round use? Any path works when capacities are whole numbers, because each round adds at least 1. But with a bad choice, the number of rounds can be as large as the answer itself, which might be millions.
  4. Choosing the path with the fewest edges, found by BFS, fixes that: the distance from the source to each node never goes down, and the number of rounds is at most O(n · e) whatever the capacities are. BFS for a path, find its bottleneck, push it and add undo room, repeat: that loop is Edmonds-Karp.

How it works

  1. Make a capacity table cap[from][to] and add each edge's capacity to it.
  2. Run BFS from source over edges with cap > 0, recording each node's parent.
  3. If the BFS never reaches sink, no more flow can get through: return flow.
  4. Walk back from sink along parent to find the bottleneck, the smallest spare capacity on the path.
  5. Walk back again: lower each forward cap by bottleneck and raise each undo cap by the same amount.
  6. Add bottleneck to flow and search for another path.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function maxFlow(n, edges, source, sink) {
  2. const cap = Array.from({ length: n }, () => new Array(n).fill(0));
  3. for (const [from, to, capacity] of edges) cap[from][to] += capacity;
  4. let flow = 0;
  5. while (true) {
  6. const parent = new Array(n).fill(-1);
  7. parent[source] = source;
  8. const queue = [source];
  9. for (let head = 0; head < queue.length && parent[sink] === -1; head++) {
  10. const node = queue[head];
  11. for (let next = 0; next < n; next++) {
  12. if (parent[next] === -1 && cap[node][next] > 0) {
  13. parent[next] = node;
  14. queue.push(next);
  15. }
  16. }
  17. }
  18. if (parent[sink] === -1) return flow;
  19. let bottleneck = Infinity;
  20. for (let v = sink; v !== source; v = parent[v]) bottleneck = Math.min(bottleneck, cap[parent[v]][v]);
  21. for (let v = sink; v !== source; v = parent[v]) {
  22. cap[parent[v]][v] -= bottleneck;
  23. cap[v][parent[v]] += bottleneck;
  24. }
  25. flow += bottleneck;
  26. }
  27. }

How fast it is

TimeO(n * e) rounds of BFS
Extra memoryO(n²)

Edmonds-Karp needs at most O(n * e) augmenting paths, each found by one BFS. The capacity table has one cell for every pair of nodes.

  • Best caseO(n²)

    The sink can't be reached at all, so one BFS over the n by n table ends it. Building the table already costs n².

  • Average caseO(k · n²)

    k is the number of rounds. Each round is one BFS scanning matrix rows, n² steps, and typical inputs need only a few rounds, far below the bound.

  • Worst caseO(n³ · e)

    Inputs built to force about n · e rounds, each with a full n² BFS. It's a bound from theory; real inputs rarely come close.

Common mistakes

  • Leaving out the undo edges. The greedy paths can then get stuck below the true maximum.
  • Overwriting cap[from][to] instead of adding to it when the same edge appears twice.
  • Using DFS with no limits on graphs with large capacities, which can need a huge number of rounds. BFS (Edmonds-Karp) keeps it bounded.
  • Forgetting that the matrix makes memory grow with n². For many thousands of nodes, use adjacency lists with paired edge objects.

When to use it

Look for these clues in a problem:

  • Edges have capacities, limits, or bandwidth, and the question asks for the most that can get through.
  • You need to pair items from two groups as much as possible, with each item used at most once (bipartite matching).
  • The question asks for the fewest edges or the cheapest set of edges to cut so the source can't reach the sink (min cut equals max flow).
  • You need the most paths from one node to another that share no edge.

Check yourself

Answer each one in your head first, then open it.

Why does pushing flow add room to the opposite direction?

So a later path can cancel some of that flow and send it elsewhere. Without it, an early choice can block the true maximum, as the greedy method stuck at 4 in the trace shows.

Why use BFS rather than any path search?

Shortest paths guarantee at most O(n · e) rounds whatever the capacities are. Any path can need as many rounds as the answer's size.

When BFS fails, how do you find the minimum cut?

Take the nodes BFS reached. The original edges from them to unreached nodes are all full, and their capacities add up to the maximum flow.

In the trace, how much flow ends up on the edge 3 → 1?

2. Round 2 sent 3 units along it, and round 3 cancelled 1 by pushing along the undo edge 1 → 3.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule kept after every round: the flow on each original edge, which is its capacity minus its cap, stays between 0 and the capacity, and every node except the source and sink has as much flow in as out. A round adds bottleneck along a whole path, entering and leaving each middle node by the same amount, and bottleneck is no larger than any cap on the path, so no cap goes below 0.

When BFS can't reach the sink, call the set of reached nodes S. Every edge from S to the rest has cap 0. For an original edge, that means it's full. For an undo edge, it means the matching original edge from the rest into S carries no flow. So the flow from source to sink equals the total capacity of the edges leaving S.

No flow can ever be bigger than the capacity of a cut like S, because everything that reaches the sink has to cross it. The current flow equals one cut's capacity, so it's the maximum, and that cut is the smallest. This is the max-flow min-cut theorem. The loop ends because Edmonds-Karp needs at most O(n · e) rounds.

Going deeper

3 more ideas

Why it stops at the maximum

When BFS can't reach the sink, let S be the nodes it did reach. Every original edge from S to the rest is full, and every edge coming back into S carries no flow (or its undo edge would have room). So the flow equals the total capacity of the edges leaving S. No flow can ever be bigger than the capacity of any such cut, so this flow is the maximum. This is the max-flow min-cut theorem.

Cost

Using BFS means each path found has the fewest edges, and it can be shown that this limits the number of rounds to O(n * e). This template finds neighbors by scanning a matrix row, so each BFS costs O(n²), for a total of O(n³ * e) in theory. In practice it is fast for the few hundred nodes these problems usually have; adjacency lists make each BFS O(n + e).

Matching with flow

To match reviewers to pull requests, add a source with an edge of capacity 1 to every reviewer, an edge of capacity 1 from each reviewer to each pull request they can review, and an edge of capacity 1 from every pull request to a sink. The maximum flow is the largest number of pairs, because each unit of flow is one reviewer matched to one pull request.

Work it by hand

Every step in a table, with why

Six nodes, source 0, sink 5. The third round sends flow backwards along an undo edge to reroute one unit, which the plain greedy method can't do.

n = 6, edges = [[0,3,4], [0,4,4], [3,5,1], [3,1,4], [3,2,1], [4,1,1], [1,5,3], [2,5,2]], source = 0, sink = 5

StepRoundPath or updatebottleneckflowWhat happensWhy
110→3→510BFS finds 2 edgesThe shortest path with room uses 0 → 3 (room 4) and 3 → 5 (room 1). The tightest is 1.
21cap[3][5] = 0, cap[5][3] = 111Push 1cap[0][3] drops to 3, and the undo edges 3 → 0 and 5 → 3 each gain 1.
320→3→1→531BFS finds 3 edges3 → 5 is full, so BFS goes through node 1. The rooms are 3, 4, and 3, so the bottleneck is 3.
42cap[0][3] = 0, cap[1][3] = 334Push 30 → 3 and 1 → 5 are now full. The undo edge 1 → 3 has 3 units of room.
530→4→1→3→2→514Uses undo edge 1→3Node 4 can reach 1, but 1 → 5 is full. The undo edge 1 → 3 lets it cancel some of node 3's flow into 1, and node 3 sends that unit to 2 instead. The rooms are 4, 1, 3, 1, 2.
63cap[1][3] = 2, cap[3][2] = 015Push 1Now 3 sends 2 units to 1 instead of 3, node 4 sends 1 unit to 1, and node 1 still sends 3 to the sink.
74none-5BFS reaches only 0, 40 → 3 and 4 → 1 are full, so the sink can't be reached. Return flow.

It returns 5. The nodes BFS reached last, {0, 4}, form the minimum cut: the edges leaving them, 0 → 3 (4) and 4 → 1 (1), add up to exactly 5. Without undo edges, the method stops after round 2 at 4.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Maximum flow (Edmonds-Karp)O(n³ · e)O(n²)Up to a few hundred nodes, where the short matrix code is easiest to get right.
Edmonds-Karp with adjacency listsO(n · e^2)O(n + e)Many nodes but few edges, where an n by n table would waste memory.
Dinic's algorithmO(n^2 · e)O(n + e)Large inputs or bipartite matching, where pushing many paths per BFS pays off.

Extra memory: O(n²): the cap table has a cell for every pair of nodes, plus parent and queue with n entries each.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Maximum flow (Edmonds-Karp) and the other approaches, on a scale where each line up is 10 times more steps.
  • Maximum flow (Edmonds-Karp) O(n³ · e)
  • Edmonds-Karp with adjacency lists, Dinic's algorithm O(n · e^2)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Maximum flow (Edmonds-Karp)10,0001 trillionmore than a quadrillion
Edmonds-Karp with adjacency lists1,0001 billionmore than a quadrillion
Dinic's algorithm1,0001 billionmore than a quadrillion

Inputs that need care

6 tricky inputs
source === sink
parent[sink] isn't -1, the bottleneck loop never runs, and flow grows by Infinity forever. Check for this first and return what the problem expects.
No path from source to sink
The first BFS fails and it returns 0.
Two edges a → b with capacities 2 and 3
cap[a][b] += capacity adds them to 5, which is correct: they act as one wider pipe.
Edges in both directions, a → b and b → a
Both capacities sit in the table, and undo room is added on top. The answer is still correct.
Capacities with decimals, like 0.1
The loop still ends, but rounding can leave tiny leftovers like 1e-17 that count as room. Scale to whole numbers, or compare with a small tolerance.
Undirected pipes
Add each pipe as two directed edges, each with the full capacity.

Variations and follow-ups

Twists interviewers add

Finding the minimum cut

After the last BFS, parent marks the nodes still reachable from the source. The original edges from those nodes to unreached nodes are the cut: the cheapest set of edges whose removal separates source from sink.

Node limits and disjoint paths

With every capacity set to 1, the maximum flow is the number of paths from source to sink that share no edge. To limit how much passes through a node, split it into an "in" node and an "out" node joined by an edge with that limit.

Dinic's algorithm

Run one BFS to label each node's distance, then push flow along many shortest paths at once before searching again. It takes O(n² · e) in general and is much faster on matching problems.

Cheapest maximum flow

If each edge also has a cost per unit, find each augmenting path with a shortest-path search on costs, like Bellman-Ford, with undo edges getting the negative cost. The result is the maximum flow with the lowest total cost.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from capacities, limits, or bandwidth plus "the most that can get through", from "match as many pairs as possible", or from "the fewest edges to cut so a can't reach b". Saying "min cut equals max flow" shows you see the link.
  • Explain undo edges with a concrete reroute, like round 3 of the trace: "pushing back along 1 → 3 means node 3 sends less to node 1 and sends that unit to node 2 instead".
  • Test by hand a graph where the first path blocks a better plan, and check that a later round uses an undo edge. Also test a graph where the sink can't be reached, which must return 0.
  • Expect "how do you turn matching into flow?". Answer: a source with capacity 1 to each left item, capacity 1 from each left item to each right item it may pair with, and capacity 1 from each right item to the sink. The maximum flow is the largest number of pairs.

Where frontend code uses it

The same idea in real UI code
  • Assignment features such as matching reviewers to pull requests or mentors to students, where each person can take only a limited number.
  • Capacity planning dashboards that compute how much traffic can get from users to a backend through CDN nodes and links with bandwidth limits.
  • Scheduling tools that fill time slots or rooms as fully as possible under per-slot and per-person limits.

Related algorithms