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 comparison model, so we cannot maintain such a total order if we want faster running time.
Such a sorting barrier was believed to exist for many problems, and people started to try to break it since 1970s. Prof. Andrew Yao gave a minimum spanning tree algorithm with running time O(m loglog n) in 1975, which is further improved to randomized linear time by Karger, Klein & Tarjan in 1990s. Faster algorithms for single-source bottleneck path and nondecreasing path problems were also found. However, 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 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 small number of edges. Since the shortest path will form a tree, if many vertices have shortest paths with large number of edges, then during the procedure the number of vertices which 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 contributes to the research.
Paper Link: //arxiv.org/abs/2504.17033
Correspondent: Yueliang Mona Jiang
Editor: Xiamin Lv
Reviewer: Xiongfeng Ma
