  In the {\em distributed all-pairs shortest paths} problem (APSP), every node
in the weighted undirected distributed network (the CONGEST model) needs to
know the distance from every other node using least number of communication
rounds (typically called {\em time complexity}). The problem admits
$(1+o(1))$-approximation $\tilde\Theta(n)$-time algorithm and a nearly-tight
$\tilde \Omega(n)$ lower bound [Nanongkai, STOC'14; Lenzen and Patt-Shamir
PODC'15]\footnote{$\tilde \Theta$, $\tilde O$ and $\tilde \Omega$ hide
polylogarithmic factors. Note that the lower bounds also hold even in the
unweighted case and in the weighted case with polynomial approximation
ratios~\cite{LenzenP_podc13,HolzerW12,PelegRT12,Nanongkai-STOC14}.}. For the
exact case, Elkin [STOC'17] presented an $O(n^{5/3} \log^{2/3} n)$ time bound,
which was later improved to $\tilde O(n^{5/4})$ [Huang, Nanongkai, Saranurak
FOCS'17]. It was shown that any super-linear lower bound (in $n$) requires a
new technique [Censor-Hillel, Khoury, Paz, DISC'17], but otherwise it remained
widely open whether there exists a $\tilde O(n)$-time algorithm for the exact
case, which would match the best possible approximation algorithm.
  This paper resolves this question positively: we present a randomized (Las
Vegas) $\tilde O(n)$-time algorithm, matching the lower bound up to
polylogarithmic factors. Like the previous $\tilde O(n^{5/4})$ bound, our
result works for directed graphs with zero (and even negative) edge weights. In
addition to the improved running time, our algorithm works in a more general
setting than that required by the previous $\tilde O(n^{5/4})$ bound; in our
setting (i) the communication is only along edge directions (as opposed to
bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in
{1, 2, ... poly(n)}). ...
