Abstract: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.
| Comments: | 17 pages |
| Subjects: | Data Structures and Algorithms (cs.DS) |
| ACM classes: | F.2.2 |
| Cite as: | arXiv:2504.17033 [cs.DS] |
| (or arXiv:2504.17033v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2504.17033 arXiv-issued DOI via DataCite |
Submission history
From: Ran Duan [view email]
[v1]
Wed, 23 Apr 2025 18:26:39 UTC (35 KB)
[v2]
Wed, 30 Jul 2025 11:02:48 UTC (49 KB)