Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
We give a deterministic O ( m log 2/3 n )-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O ( m + n log n ) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.
Authors
- Xinkai Shu (ORCID: https://orcid.org/0000-0002-5481-6553)
- Xiao Mao (ORCID: https://orcid.org/0000-0002-1224-9730)
- Jiayi Mao (ORCID: https://orcid.org/0009-0000-5488-7813)
- Ran Duan (ORCID: https://orcid.org/0009-0007-0934-0684)
- Longhui Yin (ORCID: https://orcid.org/0000-0001-5696-5678)
Institutions
- University of Science and Technology of China (CN)
- Max Planck Institute for Informatics (DE)
- Stanford University (US)
- Tsinghua University (CN)
Publication Details
- Journal
- Journal of the ACM
- Published
- 2026-10-01
- DOI
- https://doi.org/10.1145/3849867
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- article
- Field-Weighted Citation Impact
- 0.00