Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth

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 Õ(m) work and n 1/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 Õ( √ n + D + n 2/5+o(1) D 2/5 )-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.