AI summaryⓘ
The authors study a classic problem called single-source shortest paths (SSSP), which is about finding the shortest path from one point to all others in a network where distances are nonnegative. They focus on directed graphs and create a deterministic parallel algorithm that balances work done and time taken, controlled by a parameter t. Their results match previously known tradeoffs for undirected graphs, showing similar efficiency in a more general setting.
single-source shortest pathsdirected graphsnonnegative weightsparallel algorithmwork complexityspandeterministic algorithmtradeoffShi and Spencer '99
Authors
Isaac M. Hair, George Z. Li, Jason Li, Junkai Zhang
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.