Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
By: Ran Duan , Jiayi Mao , Xiao Mao and more
Potential Business Impact:
Finds shortest paths faster than old methods.
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.
Similar Papers
Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
Data Structures and Algorithms
Finds fastest routes, but is slower in practice.
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Data Structures and Algorithms
Finds the fastest path through connected points.
Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
Data Structures and Algorithms
Finds two separate shortest paths at once.