Prof. Duan Ran’s research team from the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University has explored the classic “Single-Source Shortest Path Problem (SSSP)” in graph theory algorithms, earning the Best Paper Award at the STOC 2025 conference.

Dijkstra’s Algorithm is the most classic algorithm for solving the SSSP problem, which is named after the Dutch computer scientist Edsger Dijkstra. Variants of Dijkstra’s algorithm can also work on other problems, such as single-source bottleneck path, nondecreasing path, and minimum spanning tree (Dijkstra-Jarník-Prim's algorithm). Dijkstra’s algorithm is like a dynamic programming procedure with ordering of vertices by distances, so the byproduct of Dijkstra’s algorithm is a total order of all vertices by distances from the source. But sorting takes Θ(n log n) time in the comparison model, so we cannot maintain such a total order if we want faster running time.

Since the 1970s, attempts have been made to break through this sorting barrier, which was thought to exist for many problems. In 1975, Professor Andrew Yao presented a minimum spanning tree algorithm with a running time of O(m loglog n). Karger, Klein, and Tarjan improved it to randomized linear time in the 1990s. Faster algorithms for single-source bottleneck path and nondecreasing path problems were also found. However, the shortest path problem was considered to be much harder since it needs addition operations besides comparisons.

This new paper gives the first result to break the O(m + n log n) time bound of Dijkstra’s algorithm on directed graphs. This new method combines the ideas of the Bellman-Ford algorithm and the recursive partial ordering method in Duan, Lyu, Wu and Xie’s bottleneck path algorithm. Bellman-Ford algorithm performs a full dynamic programming every step without sorting, so it is fast for paths with a small number of edges. Since the shortest path will form a tree, if many vertices have shortest paths with a large number of edges, then during the procedure the number of vertices that need to be sorted can be reduced. Although this recursive algorithm constructs a hierarchy of vertices by partial ordering of distances, it is much simpler than previous hierarchy-based algorithms for SSSP.

In 2024, Turing Award recipient Robert Tarjan and his collaborators published a paper proving the universal optimality of Dijkstra's algorithm for the "distance ordering problem." This work won the Best Paper Award at FOCS 2024. We know Dijkstra's algorithm not only solves the single-source shortest path problem but also sorts all vertices by their distances from the source. However, the new algorithm developed by Duan Ran's team avoids fully sorting all vertices, resulting in a faster solution for the shortest path problem. Given the importance of the shortest path problem, a faster algorithm holds significant theoretical and practical value.

The corresponding author of this paper is Associate Professor Duan Ran from the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. Co-authors include the alumnus of the IIIS Yao Class Shu Xinkai, IIIS graduate students Mao Jiayi and Yin Longhui. The Ph.D. student Mao Xiao from Stanford University also contributed to the research.

Link to publication: https://arxiv.org/abs/2504.17033

Editor: Li Han