We study computing { \em all-pairs shortest paths} (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from every other node using communication. The problem admits $(1+o(1))$-approximation $\tilde O(n)$-time algorithms ~\cite{ LenzenP-podc15,Nanongkai-STOC14}, which are matched with $\tilde \Omega(n)$-time lower bounds~\cite{ Nanongkai-STOC14,LenzenP_stoc13,FrischknechtHW12}\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.}. No $\omega(n)$ lower bound or $o(m)$ upper bound were known for exact computation. In this paper, we present an $\tilde O(n^{ 5/4})$-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive $O(m)$-time algorithm when the network is not so sparse. Our result also holds for the case where edge weights are { \em asymmetric} (a.k.a. the directed case where communication is bidirectional). Our techniques also yield an $\tilde O(n^{ 3/4}k^{ 1/2}+n)$-time algorithm for the { \em $k$-source shortest paths} problem where we want every node to know distances from $k$ sources; this improves Elkin's recent bound~\cite{ Elkin-STOC17} when $k=\tilde \omega(n^{ 1/4})$.
Categories: cs.DC cs.DS