# Improved Massively Parallel Shortest Path Computation

Preprint · Yi-Jun Chang, Shaun Quek

- Archive id: arxiv:2610.16787
- Published: 2026-10-12
- arXiv: https://arxiv.org/abs/2610.16787
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.16787
- PDF: https://arxiv.org/pdf/2610.16787
- Provenance: arxiv

## Abstract

We present new algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model. Specifically, we construct an $a$-approximate Single-Source Shortest Path (SSSP) oracle: Given a query consisting of a source vertex $u \\in V$, the oracle returns $a$-approximate distances $δ(u,v)$ for all $v \\in V$. Fix an $n$-vertex weighted undirected graph. We consider two regimes of the MPC model: the near-linear regime, where each machine has $\\tildeΘ(n)$ memory, and the heterogeneous regime, where all machines have $Θ(n^γ)$ memory for some constant $γ\\in (0,1\]$, except for a single machine with $\\tildeΘ(n)$ memory. We develop randomised algorithms that construct $O(1)$-approximate SSSP oracles in $O(\\log\\log n)$ rounds in the near-linear regime and in $O(\\log^2\\log n)$ rounds in the heterogeneous regime. These oracles answer distance queries in $O(1)$ rounds. Our results improve upon the recent work of Dory and Matar (SPAA 2024) which, for the same total memory, requires $\\left(\\log\\log n\\right)^{2+O(1/γ)}$ rounds and applies only to unweighted graphs in the heterogeneous setting. We say that $\\tilde N\_k(u)$ is the approximate $k$-nearest neighbourhood of a vertex $u$ if there exists an approximate distance estimate $δ$ such that $\\tilde N\_k(u)$ consists of the $k$ vertices closest to $u$ according to $δ$, breaking ties by vertex ID. The main technical ingredient is a new method for efficiently computing approximate $n^{O(γ)}$-nearest neighbourhoods in the heterogeneous MPC model in $O(\\log^2\\log n)$ rounds.

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