Ford-Fulkerson is the general method underneath every one of this site's max-flow entries: given a flow network (a directed graph where every edge has a capacity, plus a source and a sink), repeatedly find any path from source to sink with spare capacity left along its entire length, push as much flow as the tightest edge on that path allows — its bottleneck — and repeat until no such path remains. Alongside the forward capacity, every unit of flow pushed also opens a same-sized reverse residual edge, representing "this unit could be undone" — without it, an early path choice can permanently lock out a better combination (see Pitfalls). Edmonds-Karp is this exact method with one added rule: always take the augmenting path with the fewest edges, found by breadth-first search. This page is about the method with that rule removed — what stays true when the path is chosen by any means at all, and what breaks.
Four nodes, source S to sink T, five directed edges each labeled
flow/capacity. S→A, S→B, A→T, and
B→T all carry capacity 4; one thin bridge, A→B, carries capacity 1. Pick a
path-choice rule below, then press Step or Run to repeatedly find an
augmenting path under that rule, push 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 matching minimum cut, same as Edmonds-Karp's own page.
Switch the rule and press Reset: the bridge-preferring rule always chooses whichever available path crosses the thin A→B edge (forward or, once that's saturated, its reverse residual edge) over a direct S→A→T or S→B→T path, and takes 8 augmentations — one unit of flow at a time — to reach the max flow of 8. Shortest-path-first, Edmonds-Karp's own rule, never touches the bridge at all: it finds the two length-2 paths S→A→T and S→B→T directly and reaches the identical 8 in 2 augmentations. Same graph, same final answer, four times the work — purely from which path got chosen first.
The augmenting path theorem is what makes Ford-Fulkerson correct regardless of path choice: a flow is maximum if and only if its residual graph has no remaining path from source to sink. So "keep finding augmenting paths until none are left" always terminates at the true maximum, no matter which path gets picked at each step — there's nothing in the method that prefers a short path over a long one, or a "sensible-looking" one over an awkward one. For integer capacities, it also always terminates: every augmentation raises the total flow by at least 1, and the total is capped above by the sum of the source's outgoing capacities, so the number of augmentations can never exceed that sum. That's a real bound — just not one that depends on the graph's size the way Edmonds-Karp's BFS rule does. A network whose capacities are large relative to its node and edge count can force far more augmentations than a graph-size-only bound would ever predict, exactly what the demo above measures directly on a network small enough to step through by hand.
Edmonds-Karp's fix isn't a different method — it's the same method with the path-choice step pinned down:
always shortest, by number of edges, found by plain breadth-first search of the residual graph. That single
constraint is what turns "eventually finishes" into "finishes within O(VE) augmentations,
regardless of what the capacities are" (see that page's own Complexity section for the argument). Every other
augmenting-path entry on this site — Dinic's algorithm,
Minimum-Cost Maximum Flow — also picks a specific rule for
the same reason: "any path" is enough for correctness, never enough for a useful speed guarantee.
The bare method, with an unspecified findPath — plug in breadth-first search and this
becomes Edmonds-Karp; plug in depth-first search, or the demo's own
bridge-preferring rule, and it's still correct, just not equally fast:
function fordFulkerson(numNodes, edges, s, t, findPath) {
// edges: [{ a, b, cap }, ...] — directed, a → b
// findPath(cap, flow, s, t) returns an array of node indices from s to t
// with positive residual capacity on every edge, or null if none exists.
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 path = findPath(cap, flow, s, t);
if (!path) break; // no augmenting path left — done, this is the max flow
let bottleneck = Infinity;
for (let i = 0; i < path.length - 1; i++) {
bottleneck = Math.min(bottleneck, cap[path[i]][path[i + 1]] - flow[path[i]][path[i + 1]]);
}
for (let i = 0; i < path.length - 1; i++) {
const u = path[i], v = path[i + 1];
flow[u][v] += bottleneck;
flow[v][u] -= bottleneck; // opens the reverse residual edge
}
total += bottleneck;
}
return total;
}The path-choice rule is not an implementation detail — it changes how many augmentations the
method needs by a factor that grows with the capacities themselves. Verified directly on the demo's
own four-node network above: with capacities 4 on the four outer edges and 1 on the thin A→B bridge, a rule
that always prefers a path using the bridge takes exactly 8 augmentations (one unit of flow
each) to reach the max flow of 8, alternating S→A→B→T and S→B→A→T (the second using the
bridge's reverse residual edge) until both outer S-side edges are saturated. Edmonds-Karp's breadth-first
rule reaches the identical 8 in 2 augmentations, because a length-2 path never needs the
longer bridge route at all. Scale every outer capacity from 4 to C and the bridge-preferring
rule's augmentation count scales to 2C right along with it — worse and worse relative to
Edmonds-Karp's fixed 2, with the graph's own size never changing.
Reverse residual edges aren't an optimization — they're required for correctness, and this page's demo relies on them the same way Edmonds-Karp's does: the bridge-preferring rule's second augmenting path, S→B→A→T, only exists because pushing flow on A→B earlier opened a B→A reverse edge to undo it. Skip that reverse edge and a rule that happens to send the first unit of flow through the bridge gets permanently stuck below the true maximum — see Edmonds-Karp's own Pitfalls for a minimal graph where this is checked directly (final flow 1 instead of the true 2).
Real-valued capacities can break the termination guarantee entirely, not just the speed.
The "every augmentation adds at least 1" 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 strictly less than the true max flow and never reaching it — a real,
documented property of the naive method, not a hypothetical. Edmonds-Karp's breadth-first 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, so it terminates in a bounded number of steps no
matter 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.
Time: O(E · F) with an adjacency-list residual graph, where F
is the value of the max flow — each path search costs O(E), and the number of augmentations is
bounded by F for integer capacities, since every augmentation raises the total by at least 1.
This demo represents the graph as a dense V×V capacity matrix rather than adjacency lists (same
choice Edmonds-Karp's own demo makes), so each search costs O(V²) here, for a total of
O(V² · F). The key difference from Edmonds-Karp's O(VE²) (or
O(V³) on this same dense representation): that bound depends only on the graph's own size,
this one depends on F — and F can be made arbitrarily large relative to
V and E by simply raising the capacities, which is exactly what the demo's capacity
slider-free "scale C" argument above shows. Space: O(V²) for the capacity and
flow matrices as implemented here, or O(V + E) with adjacency lists.
See Choosing a Network Flow Algorithm for how all eleven of the site's Network Flow entries compare side by side, and why a specific path-choice rule — Edmonds-Karp's breadth-first search, or Dinic's batched version of the same idea — is what turns this page's general method into something worth actually running on a large graph.