# Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds

Preprint · Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak

- Archive id: arxiv:1708.03903
- Published: 2017-08-13
- arXiv: https://arxiv.org/abs/1708.03903
- Source URL: https://arxiv.org/abs/1708.03903
- PDF: https://arxiv.org/pdf/1708.03903
- Provenance: arxiv

## Abstract

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 Ω(n)$-time lower bounds~\\cite{Nanongkai-STOC14,LenzenP\_stoc13,FrischknechtHW12}\\footnote{$\\tilde Θ$, $\\tilde O$ and $\\tilde Ω$ 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 $ω(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 ω(n^{1/4})$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.