The site's eleven Network Flow entries don't all answer the same question either. Ford-Fulkerson, Edmonds-Karp, Dinic's algorithm, and Push-Relabel all compute the identical number — the maximum flow a network can carry from source to sink — Edmonds-Karp, Dinic's, and Push-Relabel by three genuinely different mechanisms, Ford-Fulkerson underneath all three of them as the shared method none of the three invented from scratch. But Bipartite Matching and Hopcroft-Karp both answer a different question — how many non-conflicting pairs, not how much flow — one by reducing to max flow, the other directly; and Hungarian Algorithm and Minimum-Cost Maximum Flow add a notion of cost that plain max flow doesn't have at all. So this guide splits the same way the MST and Non-Comparison Sort guides did: which of the first three actually computes your max flow fastest, which of the pairing pair fits without a flow network, and when one of the last two is the question you meant to ask instead.
All three ways below are specializations of one shared idea, Ford-Fulkerson's general method: repeatedly find a path from source to sink with spare capacity, push its bottleneck, repeat until none remain. Ford-Fulkerson itself is correct for any rule for picking that path — the residual graph (a reverse edge opens for every unit of forward flow, so an early choice can always be partly undone) is what makes that true regardless of which path gets picked. What "any rule" doesn't give you is a useful speed guarantee: verified directly on a small four-node network, a rule that happens to prefer an awkward path takes 8 augmentations where a better rule needs only 2 to reach the identical answer — see Ford-Fulkerson's own demo. Edmonds-Karp, Dinic's, and Push-Relabel are three different answers to "so what rule should it be," not three different base methods.
Edmonds-Karp, Dinic's, and Push-Relabel never disagree on the answer — run all three on this site's own six-node, eight-edge demo network and every one lands on the identical max flow, 15, and the identical min cut. Verified directly against the shipped code, not just eyeballed: Edmonds-Karp reaches 15 via 3 augmenting paths, one breadth-first search each; Dinic's finds the same 3 augmenting paths but batches them into 2 successful phases — phase 1 alone accounts for 2 of the 3 — plus a third, final phase that finds nothing and confirms the run is over, exactly what its own Pitfalls section describes. The choice among the three is entirely about mechanism and cost, not correctness.
Push-Relabel is the odd one out among the three, and it's the
only one that answers yes: instead of searching the residual graph for a path before pushing anything (what
Edmonds-Karp and Dinic's both do, every single time), it lets flow overflow at individual nodes on purpose and
fixes each overflow with a strictly local push-or-relabel decision — "no node ever needs to know what's
happening three hops away," per its own page. That's a real structural difference, not just a speed
difference: Edmonds-Karp and Dinic's both need to see the whole residual graph at least once before moving
any flow at all; Push-Relabel never does. The cost of that locality is that its generic version doesn't
automatically win on raw complexity — with no particular rule for which active node to work next, it shares
Dinic's own O(V²E) bound exactly. Only a smarter active-vertex rule pulls it ahead: FIFO ordering
reaches O(V³), and always picking the highest-labeled active vertex reaches
O(V²√E), "the standard textbook bound and the one usually meant by 'push-relabel' without
further qualification." Reach for it when the setting genuinely can't afford a global search step before
every push — not just because it sounds more sophisticated than the other two.
Once locality isn't the constraint, it's Edmonds-Karp against
Dinic's, and the two never disagree on mechanism, only on how
much of the residual graph gets re-searched between augmenting paths. Edmonds-Karp pays for a fresh
O(E) breadth-first search on every single augmenting path — three paths, three searches.
Dinic's keeps the same BFS-shortest-path idea but batches every path a phase's level graph can support into
one blocking flow before paying for another search — the same three paths, two successful
searches. That difference in how many times the whole graph gets rescanned is exactly what separates
Edmonds-Karp's O(VE²) from Dinic's O(V²E) — "strictly better... whenever
V < E, which is most graphs worth calling sparse," per Dinic's own Complexity section. Since
almost any real, connected graph has more edges than nodes, Dinic's is the practical default whenever
performance is a real constraint. The gap widens further on unit-capacity graphs specifically — exactly
what Bipartite Matching's reduction constructs —
where Dinic's drops to O(E√V), "the textbook default for matching problems specifically, not
just a generic max-flow fallback."
Edmonds-Karp's own role, then, is less "the practical pick" and more "the simplest correct baseline" — one
clean move, repeated: breadth-first search, push the bottleneck, repeat. Both Dinic's and Push-Relabel's own
pages build directly on Edmonds-Karp's residual-graph idea rather than inventing a new one, which is exactly
why it's worth understanding first even though it's rarely the fastest choice once E genuinely
outgrows V.
Bipartite Matching isn't a fourth way to compute a max
flow — it's a reduction, wiring a source and sink onto an unrelated-looking problem (which workers can be
paired with which jobs) so that Edmonds-Karp's own algorithm, run unmodified, finds the largest
matching as a side effect of finding the max flow. The unit-capacity structure that reduction produces is
exactly the shape Dinic's O(E√V) bound targets, so once a problem has been reduced to matching,
the choice of which max-flow algorithm backs it isn't a coin flip — Dinic's is the better engine underneath,
not Edmonds-Karp, even though the demo page itself uses Edmonds-Karp for a simpler side-by-side trace. Reach
for this reduction whenever the real question is "how many non-conflicting pairs can be made," with no
capacities or costs anywhere in the original problem statement.
Once the question really is "how many non-conflicting pairs," though,
Hopcroft-Karp is the faster way to answer it directly,
without building the flow network at all: verified on this guide's own graph, Bipartite Matching's
Edmonds-Karp reduction needs three separate augmenting-path searches, where Hopcroft-Karp's phase-based BFS
layering finds the same two of those three edges in a single pass. Both reach the identical
O(E√V) bound in the end — Bipartite Matching's by routing through Dinic's algorithm on the
reduction above, Hopcroft-Karp's by running the same phase idea directly on the bipartite graph — so the
choice is really "is a flow-network reduction already the natural framing" (keep Bipartite Matching, it's the
more general machine) versus "is this a bipartite matching problem from the start" (skip straight to
Hopcroft-Karp).
Hungarian Algorithm answers the gap Bipartite Matching's
own Pitfalls section names directly: "max flow only ever counts units, it has no notion of an edge being
preferable to another edge of the same capacity." Give every worker-job pair a cost instead of just existing
or not, and the question changes from "how many pairs" to "the cheapest way to pair everyone" — the classic
assignment problem. It doesn't touch the residual-graph machinery the other five entries all share at some
level; instead it searches only tight edges (where a pair of potentials on workers and jobs
meets the cost exactly), adjusting those potentials whenever the search stalls, at O(n³). Reach
for it specifically when the matching needs to be both complete and cheapest — a greedy
cheapest-first assignment can and does land on a valid but strictly worse pairing, per its own Pitfalls.
Minimum-Cost Maximum Flow is a third kind of "best," and it isn't Hungarian Algorithm generalized — Hungarian solves cost-weighted matching (every worker to exactly one job, a 0-or-1 pairing); this solves cost-weighted flow along a general network, where one edge can carry any amount up to its capacity. It reuses Edmonds-Karp's own residual-graph machine almost unchanged, swapping the BFS shortest-by-hops rule for a cheapest-by-cost path search — a substitution with a real consequence, since a reverse residual edge undoes flow that already cost something to send, giving it negative cost. That rules out plain Dijkstra outright: on a minimal 3-node graph with one negative reverse edge, Dijkstra finalizes a node too early and silently reports a shortest path 4 short of the true answer, no error raised anywhere. Bellman-Ford (or SPFA) is what the reference implementation actually uses instead, and the naive result is pseudo-polynomial, not polynomial — "the same honest caveat 0/1 Knapsack carries" — since the number of augmenting paths isn't bounded by graph size alone the way Edmonds-Karp's is. Reach for it when the network itself needs the cheapest way to carry its maximum load, not just a pairing.
Karger's Algorithm and the
Stoer-Wagner Algorithm both drop the source and sink
entirely — the global minimum cut asks for the fewest edges whose removal disconnects
the graph over every possible way to split it, not the cut between two fixed nodes the other
seven entries all revolve around in one form or another. It's answerable with machinery already on this
site (fix any node, run n − 1 max-flow computations against every other node as sink, keep
the smallest — always correct, first try), but these two reach the same number two completely different
ways, and disagree with each other on the tradeoff that matters: Karger's repeatedly contracts a uniformly
random remaining edge until two nodes are left — simple, and the site's first genuinely
randomized answer in this category, but a single run can and does miss the true minimum
(verified live on its own page with a 20,000-trial widget), so it needs many repeats to reach real
confidence. Stoer-Wagner instead runs a deterministic maximum adjacency search each phase, no randomness
anywhere — every run finds the true minimum, first try, at the cost of a worse per-run asymptotic bound
(O(V³) versus Karger's cheap-but-repeated O(n²) per pass). Reach for Karger's
when repeats are cheap and approximate confidence is fine; reach for Stoer-Wagner when one run has to be
exactly right.
All ten entries above answer one query per run — one source and sink, or one global minimum. The
Gomory-Hu Tree answers a batch of them: the max-flow value
between every pair of nodes in the graph, using the same budget as the global-minimum-cut trick two
paragraphs up — n − 1 max-flow computations, no more. The catch that makes it a genuinely
different technique rather than a free upgrade to that trick: the naive version fixes one source and reuses
it for every computation, which finds the correct global minimum but the wrong value for most other
pairs (verified on its own page: 22.6% of pairs wrong across 3,000 randomized graphs). Gomory-Hu's tree gets
every pair right by re-targeting each max-flow computation at the current node's own tentative parent in the
tree being built, not a fixed root, plus a reparent-and-swap bookkeeping step after each one. Reach for it
when the real question is "what's the max flow between many different pairs in this same graph," where
computing each pair separately would cost O(V²) max-flow runs instead of this page's
O(V).
| Entry | Time | Space | Answers | Reach for it when |
|---|---|---|---|---|
| Ford-Fulkerson | O(E · F), F = max flow value | O(V + E) | the max flow value | understanding the base method; never the practical pick, no bound on path choice |
| Edmonds-Karp | O(VE²) | O(V + E) | the max flow value | the simplest correct baseline; graph small enough the gap to Dinic's doesn't matter |
| Dinic's Algorithm | O(V²E), O(E√V) unit-capacity | O(V + E) | the max flow value | practical default — nearly any sparse graph, or backing a matching reduction |
| Push-Relabel | O(V²E) generic, O(V²√E) highest-label | O(V + E) | the max flow value | updates must stay local — no whole-graph search step at all |
| Bipartite Matching | O(E · min(|L|,|R|)) | O(V + E) | the largest matching size | the problem is "how many pairs," no capacities or costs involved |
| Hopcroft-Karp | O(E√V) | O(V + E) | the largest matching size | same question as Bipartite Matching, but skip the flow network entirely |
| Hungarian Algorithm | O(n³) | O(n²) | the cheapest complete assignment | matching needs a minimum-cost objective, not just size |
| Minimum-Cost Maximum Flow | O(f · VE) naive, pseudo-polynomial | O(V + E) | the cheapest flow achieving the max value | cost-weighted flow along a general network, not just pairwise assignment |
| Karger's Algorithm | O(n⁴ log n) for high-probability success, naive | O(n + m) | the global minimum cut | no fixed source/sink — where is the graph weakest, period |
| Stoer-Wagner Algorithm | O(V³) | O(V²) | the global minimum cut | same question as Karger's, but one run must be exactly right, no repeats |
| Gomory-Hu Tree | O(V) max-flow computations | O(V²) | max flow between every pair of nodes | many pairwise queries on the same graph, not just one source/sink or one global minimum |