Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths

Abstract

We revisit the single-source shortest paths (SSSP) problem on directed graphs with nonnegative real weights and give a deterministic parallel algorithm with $O(n^{1+o(1)}{t}^2+m^{1+o(1)})$ work and $\tilde{O}(n/t)$ span, for any $t\in [1,n]$. This matches (up to subpolynomial factors) the tradeoff due to [Shi and Spencer '99] for undirected graphs with nonnegative real weights.