Efficient Construction of Directed Hopsets and Parallel Single-source Shortest Paths (Abstract)
Nairen Cao, Jeremy T. Fineman, Katina Russell · 2023
The single-source shortest-path problem is as follows: given a graph with nonnegative edge weights and a designated source vertex s, return the distances from~s to each other vertex such. This paper presents a randomized parallel single-source shortest paths (SSSP) algorithm for directed graphs with non-negative integer edge weights that solves the exact SSSP problem in O (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.