# Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time

Preprint · Aaron Bernstein, Danupon Nanongkai

- Archive id: arxiv:1811.03337
- Published: 2018-11-08
- arXiv: https://arxiv.org/abs/1811.03337
- Source URL: https://arxiv.org/abs/1811.03337
- PDF: https://arxiv.org/pdf/1811.03337
- Provenance: arxiv

## Abstract

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Θ(n)$-time algorithm and a nearly-tight $\\tilde Ω(n)$ lower bound \[Nanongkai, STOC'14; Lenzen and Patt-Shamir PODC'15\]\\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~\\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)}). ...

_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.