# A Deterministic Distributed Algorithm for Weighted All Pairs Shortest Paths Through Pipelining

Preprint · Udit Agarwal, Vijaya Ramachandran

- Archive id: arxiv:1807.08824
- Published: 2018-07-23
- arXiv: https://arxiv.org/abs/1807.08824
- Citations: 2
- Source URL: https://arxiv.org/abs/1807.08824
- PDF: https://arxiv.org/pdf/1807.08824
- Provenance: arxiv

## Abstract

We present a new pipelined approach to compute all pairs shortest paths (APSP) in a directed graph with nonnegative integer edge weights (including zero weights) in the CONGEST model in the distributed setting. Our deterministic distributed algorithm computes shortest paths of distance at most $Δ$ for all pairs of vertices in at most $2 n \\sqrtΔ + 2n$ rounds, and more generally, it computes h-hop shortest paths for k sources in $2\\sqrt{nkh} + n + k$ rounds. The algorithm is simple, and it has some novel features and a nontrivial analysis.It uses only the directed edges in the graph for communication. This algorithm can be used as a base within asymptotically faster algorithms that match or improve on the current best deterministic bound of $\\tilde{O}(n^{3/2})$ rounds for this problem when edge weights are $O(n)$ or shortest path distances are $\\tilde{O}(n^{3/2})$.

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