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

Preprint · Isaac M. Hair, George Z. Li, Jason Li, Junkai Zhang

- Archive id: arxiv:2607.19342
- Published: 2026-07-21
- arXiv: https://arxiv.org/abs/2607.19342
- Source URL: https://arxiv.org/abs/2607.19342
- PDF: https://arxiv.org/pdf/2607.19342
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.