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

2026/07/21 by Isaac M. Hair, George Z. Li, Jason Li +1
#cs.DS

paper · pdf

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² + m^1+o(1)) work and O(n/t) span, for any t ∈ [1, n]. This matches (up to subpolynomial factors) the tradeoff due to [Shi and Spencer '99] for undirected graphs with nonnegative real weights.

Related

• Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
• A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
• A Faster Directed Single-Source Shortest Path Algorithm
• Single-Source Shortest Paths with Negative Real Weights in O(mn^8/9) Time
• Negative-Weight Single-Source Shortest Paths in Near-linear Time