We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take \(\textrm{poly}(\log {\log {n}})\) rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with n vertices and m edges. Our first contribution is a \((1+\epsilon )\) -approximation algorithm for Single-Source Shortest Paths (SSSP) that takes \(\textrm{poly}(\log {\log {n}})\) rounds in the near-linear MPC model, where the memory per machine is \(\tilde{O}(n)\) and the total memory is \(\tilde{O}(mn^{\rho })\) , where \(\rho \) is a small constant. Our second contribution is a distance oracle that allows to approximate the distance between any pair of vertices. The distance oracle is constructed in \(\textrm{poly}(\log {\log {n}})\) rounds and allows to query a \((1+\epsilon )(2k-1)\) -approximate distance between any pair of vertices u and v in O(1) additional rounds. The algorithm is for the near-linear memory MPC model with total memory of size \(\tilde{O}((m+n^{1+\rho })n^{1/k})\) , where \(\rho \) is a small constant. While our algorithms are for the near-linear MPC model, in fact they only use one machine with \(\tilde{O}(n)\) memory, where the rest of machines can have sublinear memory of size \(O(n^{\gamma })\) for a small constant \(\gamma < 1\) . All previous algorithms for approximate shortest paths in the near-linear MPC model either required \(\Omega (\log {n})\) rounds or had an \(\Omega (\log {n})\) approximation. Our approach is based on fast construction of near-additive emulators, limited-scale hopsets and limited-scale distance sketches that are tailored for the MPC model. While our end-results are for the near-linear MPC model, many of the tools we construct such as hopsets and emulators are constructed in the more restricted sublinear MPC model.
