Faster method improves shortest paths in weighted undirected graphs
A Faster Undirected Single-Source Shortest Path Algorithm
Data Structures and Algorithms
Summary
Finding the shortest path from one point to all others in a network with weighted connections is a common problem in computer science. Previously, faster methods than the classic algorithm only appeared recently. The authors present an even quicker way to find these shortest paths in networks where connections have weights and directions don’t matter. Their key new idea is a simple tool that quickly finds the closest special points to every location in the network. This improvement speeds up the overall process by a small but meaningful amount.
What this means in practice
- •For network algorithm developers: Optimize shortest path computations in large undirected weighted networks using the authors’ improved algorithm for faster results.
- •For it infrastructure planners: Plan efficient routing in computer networks or transport systems by leveraging faster shortest-path distance calculations enabled by improved algorithms.
Authors
Avi Kadria, Liam Roditty
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.