A Faster Directed Single-Source Shortest Path Algorithm
Abstract
This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\sqrt{mn\log n\log \log n})$, which is $O(m\sqrt{\log n\log \log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\log^{2/3} n)$ time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Graph Theory and Algorithms
Algorithms and Data Compression
Publication details
- Journal / source
- MPG.PuRe (Max Planck Society)
- Publication date
- 8 February 2026
- Language
- EN