In this paper, we present a new randomized O(1)-approximation algorithm for the All-Pairs Shortest Paths (APSP) problem in weighted undirected graphs that runs in just \(O(\log \log \log n)\) rounds in the Congested-Clique model. Before our work, the fastest algorithms achieving an O(1)-approximation for APSP in weighted undirected graphs required \({{\,\textrm{poly}\,}}(\log n)\) rounds, as shown by Censor-Hillel, Dory, Korhonen, and Leitersdorf (PODC 2019 & Distributed Computing 2021). In the unweighted undirected setting, Dory and Parter (PODC 2020 & Journal of the ACM 2022) obtained O(1)-approximation in \({{\,\textrm{poly}\,}}(\log \log n)\) rounds. By terminating our algorithm early, for any given parameter \(t \ge 1\) , we obtain an O(t)-round algorithm that guarantees an \(O\left( \log ^{1/2^t} n\right)\) approximation in weighted undirected graphs. This tradeoff between round complexity and approximation factor offers flexibility, allowing the algorithm to adapt to different requirements. In particular, for any constant \(\varepsilon> 0\) , an \(O\left( \log ^\varepsilon n\right)\) -approximation can be obtained in O(1) rounds. Previously, O(1)-round algorithms were only known for \(O(\log n)\) -approximation, as shown by Chechik and Zhang (PODC 2022). A key ingredient in our algorithm is a lemma that, under certain conditions, allows us to improve an a-approximation for APSP to an \(O(\sqrt{a})\) -approximation in O(1) rounds. To prove this lemma, we develop several new techniques, including an O(1)-round algorithm for computing the k-nearest nodes, as well as new types of hopsets and skeleton graphs based on the notion of k-nearest nodes.
