{"id":"arxiv:2607.19342","kind":"preprint","title":"Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths","authors":["Isaac M. Hair","George Z. Li","Jason Li","Junkai Zhang"],"author_count":4,"year":2026,"published":"2026-07-21","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2607.19342","nct_id":null,"source_url":"https://arxiv.org/abs/2607.19342","archive_url":"https://space-kitty.com/papers/arxiv:2607.19342","updated":"2026-07-21","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2607.19342","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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}