Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth
Nairen Cao, Jeremy T. Fineman · Society for Industrial and Applied Mathematics eBooks · 2023
This paper presents a randomized parallel single-source shortest paths (SSSP) algorithm for directed graphs with non-negative integer edge weights that solves the problem exactly in O(m) work and n1/2+o(1) span, with high probability. All previous exact SSSP algorithms with nearly linear work have linear span, even for undirected unweighted graphs. Our main technical contribution is to show a reduction from the exact SSSP to directed hopsets [6] using the iterative gradual rounding technique [9]. An (h, ε)-hopset is a set of weighted edges (sometimes called shortcuts) that when added to the graph admit h-hop paths with weights no more than (1 + ε) times the true shortest path distances. Furthermore, we show how to combine this algorithm with Forster and Nanongkai's framework [15] to improve the distributed exact SSSP algorithm. Specifically, we obtain an -round algorithm in the CONGEST model for exact SSSP in directed graphs with non-negative integer edge weights, where D is the unweighted diameter of the underlying undirected graph.