A flow network is a directed graph where every edge carries a capacity — the most it can carry at once — plus one designated source (where flow originates) and one sink (where it's consumed). The maximum flow problem asks: how much can get from source to sink at the same time, obeying two rules everywhere else — no edge carries more than its capacity, and every other node passes along exactly as much as it receives, no more, no less? This is a third, structurally different question from the other two "best thing in a weighted graph" problems this site already covers: Minimum Spanning Trees ask for the cheapest way to connect everything, Shortest Paths ask for the cheapest way between two points — max flow asks for the most a whole network can carry between two points at once, and the answer usually uses every path from source to sink, not just one.
The classic method — Ford-Fulkerson — is beautifully simple to state: while some path still has spare capacity all the way from source to sink, push as much flow along it as the tightest edge on that path allows, then repeat. The one subtlety that makes this provably correct rather than just greedy is the residual graph: alongside "how much more can flow forward on this edge," every unit of flow already sent also opens up a same-sized reverse edge, representing "this much flow could be undone." Without that reverse option, an early path choice can permanently lock out a better combination — see Pitfalls below for a real, checked case. Ford-Fulkerson itself never says which path to pick when several exist — Edmonds-Karp is Ford-Fulkerson with one specific rule: always take the shortest augmenting path, by number of edges, found with a plain breadth-first search of the residual graph. That single choice is what turns "eventually finishes" into "finishes within a number of steps bounded by the graph's own size" — see Complexity below.
Six nodes, source S to sink T, eight directed edges each labeled
flow/capacity. Press Step or Run to repeatedly find the
shortest S→T path with spare capacity (breadth-first, exactly Edmonds-Karp's rule), push flow equal to
that path's tightest remaining edge — its bottleneck — and repeat. A black-bordered node
and thick black edge mark the path just found; orange marks any edge currently carrying flow. When no path
remains, the demo reveals the minimum cut: every node still reachable from S in the final
residual graph gets an orange border, and the edges crossing from that group to the rest — dashed in the
diagram — turn out to have exactly the same total capacity as the max flow just found. That equality is
the max-flow min-cut theorem, and this page checks it live rather than just stating it.
The residual graph at any point has, for every edge u→v with capacity c and
current flow f, a forward residual edge of capacity c − f (room left to push more)
and a reverse residual edge of capacity f (room to undo what's already there). "Find an
augmenting path" just means "find any S→T path in this residual graph using only edges with positive
residual capacity" — a plain reachability search, identical in shape to
breadth-first search on any other graph. Ford-Fulkerson is correct with
any rule for picking that path, including a careless one — it terminates (for integer capacities)
because every augmentation increases the total flow by at least 1, and the total flow is bounded above by
the sum of the source's outgoing capacities. But "terminates" says nothing about how many
augmentations that takes, and a careless rule can take a lot of them (see Pitfalls). Edmonds-Karp's
BFS-shortest-path rule adds a structural guarantee on top: the length of the shortest augmenting path
never decreases from one augmentation to the next, and for any fixed path length, at most O(E)
augmentations can happen before some edge on every shortest path of that length is saturated and the
shortest path is forced to get longer. With path length bounded by O(V), that caps the total
number of augmentations at O(VE) — regardless of what the capacities actually are.
The minimum cut the demo reveals at the end isn't a separate algorithm — it falls directly out of the same final residual graph. Split the nodes into "still reachable from S" and "everything else": no edge crossing from the first group to the second can have spare residual capacity, or BFS would have followed it and T would already be reachable. So every edge crossing that split is fully saturated, and the flow across it exactly equals its total capacity — which the max-flow min-cut theorem says is also the smallest possible capacity of any way to split S from T. Max flow and min cut are always equal; this is why the algorithm can stop and declare victory the moment BFS fails to reach T, instead of needing some separate check that no better flow exists.
This algorithm also answers questions that never mention capacities at all: wire a source to one side of a bipartite graph and a sink to the other, cap every edge at 1, and Edmonds-Karp run unmodified finds a maximum matching as its max flow — see that page for the reduction and a worked example where an augmenting path has to un-match an existing pair to reach the true maximum.
Edmonds-Karp's BFS rule is what caps the augmentation count, but it still pays for a fresh O(E)
breadth-first search on every single augmenting path. Dinic's algorithm keeps the same BFS-shortest-path
idea but batches every path a single BFS's level graph can support into one "blocking flow" before paying
for another search — on this exact graph, that's 2 BFS calls instead of 3, one of them alone accounting for
two of the three augmenting paths found here.
Both of those still belong to the augmenting-path family: search globally, push, repeat. Push-relabel abandons that family entirely — no BFS at all, ever. It lets flow overflow locally at individual nodes on purpose, then fixes each overflow with a strictly local push-or-relabel decision, never needing to know what the rest of the graph looks like. All three of these only care about how much flow, never at what cost — give every edge a cost per unit as well as a capacity, and Minimum-Cost Maximum Flow reuses this exact residual-graph machine one more time, swapping BFS for Bellman-Ford so the cheapest augmenting path wins instead of the shortest one. All four still specialize Ford-Fulkerson's same general method with a specific path-choice rule — none of them invented the residual-graph idea itself.
Matches the demo above one for one — same capacity matrix, same BFS rule, same residual bookkeeping,
just without the yield points the demo uses to show every intermediate augmentation:
function edmondsKarp(numNodes, edges, s, t) {
// edges: [{ a, b, cap }, ...] — directed, a → b
const cap = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
edges.forEach(e => { cap[e.a][e.b] += e.cap; });
const flow = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
let total = 0;
while (true) {
const parent = new Array(numNodes).fill(-1);
parent[s] = s;
const queue = [s];
while (queue.length && parent[t] === -1) {
const u = queue.shift();
for (let v = 0; v < numNodes; v++) {
if (cap[u][v] - flow[u][v] > 0 && parent[v] === -1) {
parent[v] = u;
queue.push(v);
}
}
}
if (parent[t] === -1) break; // no augmenting path left — done
let bottleneck = Infinity;
for (let v = t; v !== s; v = parent[v]) {
bottleneck = Math.min(bottleneck, cap[parent[v]][v] - flow[parent[v]][v]);
}
for (let v = t; v !== s; v = parent[v]) {
flow[parent[v]][v] += bottleneck;
flow[v][parent[v]] -= bottleneck; // opens the reverse residual edge
}
total += bottleneck;
}
return total;
}The augmenting-path rule matters — a lot. Ford-Fulkerson is correct with any rule for
picking a path, but "any rule" includes catastrophically bad ones. Take a 4-node graph
S, A, B, T with S→A, S→B, A→T, and B→T all
capacity 1000, plus one thin crossing edge A→B capacity 1. A depth-first, non-BFS
Ford-Fulkerson that happens to alternate between the paths S→A→B→T and S→B→A→T
(the second using A→B's reverse residual edge) pushes only 1 unit of flow per augmentation,
because that thin edge is on both paths — it took a from-scratch simulation of exactly this alternation
2,000 augmentations to reach the true max flow of 2,000. Edmonds-Karp's BFS rule never
touches the thin edge at all — it finds the two length-2 paths S→A→T and S→B→T
directly and reaches the same 2,000 in 2 augmentations. Same graph, same final answer,
three orders of magnitude apart in how long it takes to get there — the rule for choosing a path is not a
minor implementation detail. Ford-Fulkerson's own page
ships this exact phenomenon as a live, steppable demo at a smaller scale (capacity 4, 8 augmentations
instead of 2,000) rather than only a from-scratch simulation.
Reverse residual edges aren't an optimization — they're required for correctness. Take
S, A, B, T with S→A, S→B, A→T, and B→T all
capacity 1, plus a crossing edge A→B capacity 1. If the very first augmenting path found is
S→A→B→T (bottleneck 1), that path alone already touches every node — and a "greedy" version
that never opens a reverse edge on B→A to undo that choice gets stuck there permanently, at a
final flow of 1. Checked by running the same graph with reverse edges enabled: the
algorithm finds a second augmenting path, S→B forward then A→B's reverse edge
then A→T forward — effectively re-routing that first unit of flow away from the shared edge —
and reaches the true max flow of 2. The reverse edge doesn't add flow anywhere new; it
lets the algorithm take back a choice that, in hindsight, blocked a better combination.
Real-valued capacities can break plain Ford-Fulkerson's termination guarantee entirely, not just
its speed. The "every augmentation adds at least 1" termination argument above assumes integer
capacities. With irrational capacities and an adversarial path-choice rule, Ford-Fulkerson can be
constructed to augment forever, converging toward a total that's less than the true max flow and
never reaching it. Edmonds-Karp's BFS rule sidesteps this completely — its O(VE) bound on the
number of augmentations comes from the graph's own size (path lengths and edge count), never from the
capacity values themselves, so it terminates in a bounded number of steps regardless of what the
capacities are. This page's demo only ever uses small integers, so this particular failure mode isn't
something it can show live — it's a real, documented property of the naive method worth knowing about
rather than a hypothetical; see Ford-Fulkerson's own
Pitfalls for the same caveat stated against the general method directly, not just this page's
specialization of it.
The demo's capacity/flow matrix is O(V²) space, which is fine for six nodes and
wasteful for a sparse graph with many. A real implementation on a graph with thousands of nodes
but few edges per node would use adjacency lists instead, storing residual capacity only for edges that
actually exist — the algorithm itself doesn't change, only the data structure backing "what's the residual
capacity from u to v."
Time: O(VE²) — each breadth-first search costs O(E)
(O(V²) here, since the demo represents the graph as a dense capacity matrix rather than
adjacency lists), and the number of augmentations is bounded by O(VE) as argued above, for a
total of O(VE) · O(E) = O(VE²). This is independent of the actual capacity values — unlike
naive Ford-Fulkerson, whose iteration count can depend on the capacities themselves (see Pitfalls).
Space: O(V²) for the capacity and flow matrices as implemented here, or
O(V + E) with adjacency lists — the BFS itself needs only O(V) more for the
parent array and queue.
This page's own residual-graph idea is what Dinic's, Push-Relabel, and Minimum-Cost Maximum Flow all build
on directly — see Choosing a Network Flow
Algorithm for how all eleven of the site's Network Flow entries compare side by side, and why Dinic's is the
practical default once E genuinely outgrows V.