A Faster Undirected Single-Source Shortest Path Algorithm

Abstract

The single-source shortest paths (SSSP) problem in graphs with non-negative edge weights is one of the most classic problems in algorithms. For decades, the best known running time in the comparison-addition model was the $O(m+n\log n)$ bound of Dijkstra's algorithm with Fibonacci heaps. Recently, Duan, Mao, Shu, and Yin (FOCS'23) gave a randomized $O(m{\log }^{1/2}n\log {\log }^{1/2}n)$-time algorithm for SSSP in weighted undirected graphs. For weighted directed graphs, Duan, Mao, Mao, Shu, and Yin (STOC'25) gave an $O(m{\log }^{2/3}n)$-time algorithm for SSSP. Very recently, Duan, Mao, Shu, and Yin (ICALP'26) obtained an algorithm for directed graphs whose running time matches the $O(m{\log }^{1/2}n\log {\log }^{1/2}n)$ time of the undirected case. In this paper, we present a faster algorithm for SSSP in weighted undirected graphs, giving the first improvement in running time since the FOCS'23 breakthrough of Duan, Mao, Shu, and Yin. Our algorithm runs in $O(m{\log }^{1/2}n\log {\log }^{1/4}n\log \log {\log }^{1/4}n)$ time, improving the previous running time by a factor of $(\frac{\log \log n}{\log \log \log n}{)}^{1/4}$. Our main contribution is a simple and efficient tool that computes, for every vertex, its distance to the nearest vertex in a random sample; this tool may be of independent interest.