Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Ran Duan, Jiayi Mao, Xiao Mao +2

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 m…