Improved Massively Parallel Shortest Path Computation

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 $\delta (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{\mathrm{\Theta }}(n)$ memory, and the heterogeneous regime, where all machines have $\mathrm{\Theta }(n^{\gamma })$ memory for some constant $\gamma \in (0,1]$, except for a single machine with $\tilde{\mathrm{\Theta }}(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 ${(\log \log n)}^{2+O(1\mathrm{/}\gamma )}$ 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 $\delta$ such that ${\tilde{N}}_k(u)$ consists of the $k$ vertices closest to $u$ according to $\delta$, breaking ties by vertex ID. The main technical ingredient is a new method for efficiently computing approximate $n^{O(\gamma )}$-nearest neighbourhoods in the heterogeneous MPC model in $O({\log }^2\log n)$ rounds.