  In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of
computing the max-flow between all $n\choose 2$ pairs of vertices in an
undirected graph can be solved using only $n-1$ calls to any (single-pair)
max-flow algorithm. Even assuming a linear-time max-flow algorithm, this yields
a running time of $O(mn)$, which is $O(n^3)$ when $m = \Theta(n^2)$. While
subsequent work has improved this bound for various special graph classes, no
subcubic-time algorithm has been obtained in the last 60 years for general
graphs. We break this longstanding barrier by giving an $\tilde{O}(n^{2})$-time
algorithm on general, weighted graphs. Combined with a popular complexity
assumption, we establish a counter-intuitive separation: all-pairs max-flows
are strictly easier to compute than all-pairs shortest-paths.
  Our algorithm produces a cut-equivalent tree, known as the Gomory-Hu tree,
from which the max-flow value for any pair can be retrieved in near-constant
time. For unweighted graphs, we refine our techniques further to produce a
Gomory-Hu tree in the time of a poly-logarithmic number of calls to any
max-flow algorithm. This shows an equivalence between the all-pairs and
single-pair max-flow problems, and is optimal up to poly-logarithmic factors.
Using the recently announced $m^{1+o(1)}$-time max-flow algorithm (Chen et al.,
March 2022), our Gomory-Hu tree algorithm for unweighted graphs also runs in
$m^{1+o(1)}$-time.
