# New and Simplified Distributed Algorithms for Weighted All Pairs Shortest Paths

Preprint · Udit Agarwal, Vijaya Ramachandran

- Archive id: arxiv:1810.08544
- Published: 2018-10-18
- arXiv: https://arxiv.org/abs/1810.08544
- Citations: 4
- Source URL: https://arxiv.org/abs/1810.08544
- PDF: https://arxiv.org/pdf/1810.08544
- Provenance: arxiv

## Abstract

We consider the problem of computing all pairs shortest paths (APSP) and shortest paths for k sources in a weighted graph in the distributed CONGEST model. For graphs with non-negative integer edge weights (including zero weights) we build on a recent pipelined algorithm to obtain $\\tilde{O}(λ^{1/4}\\cdot n^{5/4})$ in graphs with non-negative integer edge-weight at most $λ$, and $\\tilde{O}(n \\cdot \\bigtriangleup^{1/3})$ rounds for shortest path distances at most $\\bigtriangleup$. Additionally, we simplify some of the procedures in the earlier APSP algorithms for non-negative edge weights in \[HNS17,ARKP18\]. We also present results for computing h-hop shortest paths and shortest paths from $k$ given sources. In other results, we present a randomized exact APSP algorithm for graphs with arbitrary edge weights that runs in $\\tilde{O}(n^{4/3})$ rounds w.h.p. in n, which improves the previous best $\\tilde{O}(n^{3/2})$ bound, which is deterministic. We also present an $\\tilde{O}(n/ε^2)$-round deterministic $(1+ε)$ approximation algorithm for graphs with non-negative $poly(n)$ integer weights (including zero edge-weights), improving results in \[Nanongkai14,LP15\] that hold only for positive integer weights.

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

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

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