2 papers
cs.DS2025★ 3 cited
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao +2
We give a deterministic -time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition m…
cs.DS2023
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
Ran Duan, Jiayi Mao, Xinkai Shu +1
In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time $O(m\sqrt{\log n \cdot…