Edmonds-Karp, Dinic's
Algorithm, and Push-Relabel all answer one max-flow question at a
time: fix a source and a sink, get one number. Choosing
a Network Flow Algorithm already notes a cheap way to get the graph's single weakest point instead — fix any
one node, run n − 1 max-flow computations against every other node as sink, and the smallest of
those is the true global minimum cut, no repeats needed. The Gomory-Hu tree, described by Ralph
Gomory and Te Chiang Hu in 1961 (this page builds it via Dan Gusfield's considerably simpler 1990 construction),
answers a broader question with that exact same budget of n − 1 max-flow computations: not just the
single weakest cut, but the max-flow value between every one of a graph's n(n−1)/2 pairs of
nodes, packed into a tree with only n − 1 edges.
Gusfield's construction builds that tree incrementally. Pick any node as an arbitrary root (this page always
picks the first); every other node starts out with a tentative parent pointing at the root.
Then, one node i at a time: run one real max-flow between i and whatever it currently
points at, record that flow as i's tentative edge weight, and do two pieces of bookkeeping — any
later node still pointing at the same parent that landed on i's side of this computation's min cut
reparents to i instead (its own eventual answer is now more accurately routed through i);
and if i's parent's own parent also landed on i's side, the two edges swap places (see
Try it's own trace for exactly when and why — it happens on this page's own default graph). Every one of these
max-flow computations runs on the same, unmodified original graph — nothing shrinks or contracts between steps,
unlike Stoer-Wagner Algorithm's phase-by-phase merging for
the single global-minimum-cut question.
Six nodes, six weighted undirected edges: A-D (4), B-C (8), B-D (6), C-E (7), C-F (6), D-F (3). Press Step or Run to process nodes B through F in order: each step's max-flow computation highlights the source node (bold border) and its target parent (thin border), and shades every node on the source's side of that computation's cut. The table below the graph tracks each node's current tentative parent and weight live, including the one reparent-and-swap event this graph triggers. Once the tree is complete, use the query tool to pick any two nodes — the smallest weight on the tree path between them is checked live against a real max-flow computation on the original graph below it.
The read-off rule: the max-flow value between any two nodes u and v equals the
smallest edge weight on the unique tree path between them — never the sum, never the largest, always the
minimum. That single number is guaranteed correct for every pair (verified below), which is a genuinely different
guarantee from what a naive fix-one-source approach gives (see Pitfalls). Checked exhaustively over
every one of the 1,024 possible unweighted graphs on 5 labeled vertices (10,240 total pairs) and via 5,000
randomized weighted trials on graphs of 4-9 vertices (95,883 total pairs) against independent brute-force max-flow
on each pair — 0 mismatches, both times.
Two honest caveats worth knowing rather than assuming. First, a tree edge does not need to be a real edge in the original graph at all — it's a max-flow value, not a capacity. On this page's own demo graph, all five tree edges happen to coincide with real original edges (with different weights — the original B-D edge is capacity 6, but the tree's B-D edge is weight 9), purely because the graph is small and dense; measured across 2,000 randomized larger graphs, 24.3% of all tree edges connect a pair with no direct edge between them whatsoever. Second, this page builds the tree via Gusfield's simplification specifically because it's dramatically simpler to implement than Gomory and Hu's original 1961 construction (which contracts one side of the graph after every step) — verified here to reproduce the correct max-flow value for every pair, which is everything a query needs. The original, more involved construction additionally guarantees that the edge removed to separate any two nodes is an actual minimum cut for that pair in the original graph, a stronger property this page's simpler version doesn't claim and isn't needed for the value-lookup this page's query tool performs.
Matches the demo above one for one (with the demo's own bookkeeping variants stripped out — this is the correct, unmodified construction):
function gomoryHuTree(n, cap) {
// cap: n x n symmetric capacity matrix, node 0 is the arbitrary root
const parent = new Array(n).fill(0);
const weight = new Array(n).fill(0);
for (let i = 1; i < n; i++) {
const { flow, sSide } = maxFlowWithMinCutSide(n, cap, i, parent[i]);
const oldParent = parent[i];
weight[i] = flow;
for (let j = i + 1; j < n; j++) {
if (parent[j] === oldParent && sSide[j]) parent[j] = i;
}
const grandparent = parent[oldParent];
if (sSide[grandparent]) {
parent[i] = grandparent;
parent[oldParent] = i;
weight[i] = weight[oldParent];
weight[oldParent] = flow;
}
}
return { parent, weight }; // edge (i, parent[i]) has weight weight[i], for i = 1..n-1
}
function queryMaxFlow(n, parent, weight, u, v) {
// BFS the tree, tracking the minimum edge weight seen along the path
const adj = Array.from({ length: n }, () => []);
for (let i = 1; i < n; i++) {
adj[i].push([parent[i], weight[i]]);
adj[parent[i]].push([i, weight[i]]);
}
const seen = new Array(n).fill(false);
seen[u] = true;
const queue = [[u, Infinity]];
while (queue.length) {
const [node, minSoFar] = queue.shift();
if (node === v) return minSoFar;
for (const [next, w] of adj[node]) {
if (!seen[next]) { seen[next] = true; queue.push([next, Math.min(minSoFar, w)]); }
}
}
}The reparent-and-swap step must read the old parent before overwriting it. Computing
parent[i] = grandparent and then using parent[i] — already overwritten — to index the
second half of the swap (parent[parent[i]] = i) silently writes into the wrong slot instead of
setting the old parent's own entry. It still runs, still returns a tree of the right shape, just with one edge's
weight lost, permanently replaced by its unused initial value of 0. On this page's own default graph, that one
corrupted node is D: the buggy tree reports max-flow of 0 for every one of the 5 pairs
involving D (A-D, B-D, C-D, D-E, D-F), each falsely claiming D is fully disconnected, when the true values are
4, 9, 9, 7, and 9 — select "reparent using the parent pointer after it's already been overwritten" above and
query any pair with D to see it live. Measured more broadly: across 5,000 randomized weighted graphs (4-9
vertices, 95,509 total pairs), this bug disagreed with brute-force max-flow on 25.6% of all
pairs — not rare, and not limited to unusual graphs.
"Fix one source, run n − 1 max-flows" is a real, working algorithm — just not this one. The
Network Flow guide's own naive method for the global minimum cut (fix any node, run n − 1
max-flow computations against every other node as sink, keep the smallest) looks identical to this page's own
budget, and it's tempting to assume it's silently already building a Gomory-Hu tree, giving every pairwise answer
along the way. It isn't: fixing the source instead of using each node's current parent still finds the
correct global minimum every time (confirmed over 3,000 randomized trials, 3,000/3,000), but reports the wrong
value for almost every pair that doesn't include the fixed root. On this page's own demo graph, using this
fixed-source shortcut instead of Gusfield's reparenting gets 10 of the 15 possible pairs wrong —
every pair not involving A — each one under-reported to exactly 4 (the graph's true global minimum, and also A's
own bottleneck edge), when the true values range from 7 to 11. Select "always flow against the root" above to
see it live. Measured more broadly: 22.6% of all pairs wrong across 3,000 randomized graphs. The reparenting step
— not just the raw count of max-flow computations — is what turns a global-minimum-cut trick into a tree that
answers every pair.
Time: n − 1 max-flow computations, each run on the full, unshrunk original graph
— O(V) calls total, each costing whatever the underlying max-flow algorithm costs on the original
V and E. This page's demo and reference implementation use the same
Edmonds-Karp subroutine already on this site (O(VE²) per
call), for a combined O(V²E²) as implemented here — swapping in Dinic's Algorithm underneath instead would tighten that to
O(V²E), since nothing about Gusfield's construction depends on which max-flow subroutine answers
each call. Space: O(V²) for the dense capacity matrix each max-flow call reads,
plus O(V) for the tree's own parent/weight arrays.
Compare that O(V) max-flow calls against computing every pair's max flow independently — the
naive way to answer "what's the max flow between every pair" without this page's tree, at O(V²)
separate calls. See Choosing a Network Flow Algorithm
for how this entry compares against all ten of the site's other Network Flow pages side by side.