A new approach brings fresh momentum to "Dijkstra’s Algorithm", a decades-old fundamental problem in computer science.
Xinkai Shu receives together with colleagues a STOC 2025 Best Paper Award. Photo: Philipp Zapf-Schramm/MPI INF
Graphs are a concept from computer science used to model relationships between different entities. They are suitable for representing real-world systems such as transportation networks, social networks, or neural connections in the brain. An international research team involving the Max Planck Institute for Informatics in Saarbrücken, Germany, has now developed an algorithm that can process such graphs faster than prominent existing methods, most notably "Dijkstra’s Algorithm". For this achievement, the team was honored with a "Best Paper Award" at one of the world’s leading conferences in theoretical computer science.
Graphs can be compared to road maps. In a graph, nodes – or "vertices" – represent locations, such as cities or intersections. Lines, called "edges", connect these nodes and can be labeled with numbers representing, for example, distances, travel times, or toll costs. This creates an abstract model that represents, in this case, a real transportation network. A central problem in theoretical computer science is finding the shortest or most efficient path from one starting point to all other points in such a network. Experts refer to this as the "Single-Source Shortest-Paths Problem(SSSP)". Navigation systems solve precisely this task when calculating a route—for example, from a current location to all reachable destinations.
Simple graph showing vertices with weighted edges. Picture: AI/ ChatGPT
A fundamental algorithm for solving this problem is Dijkstra’s Algorithm, named after the Dutch computer scientist Edsger Dijkstra. Since its development in 1956, it has been considered a landmark contribution. It allows efficient determination of the lowest-cost paths through a network—measured, for example, in kilometers, minutes, or other units. The algorithm starts at a source node and gradually examines all reachable connections, always choosing the currently closest one. Once the shortest path to a point has been found, it is not changed. In this way, the search expands iteratively until all reachable points have been covered.
To improve on Dijkstra’s algorithm, the new paper takes a close look at the part that causes most of its computational cost: the interaction with a so-called "priority queue". During its execution, Dijkstra's algorithm needs to maintain the "frontier", which is the set of vertices that have been discovered but not yet fully processed — meaning their tentative shortest distance from the source is known, but the algorithm might not have fully explored their neighboring vertices yet. These frontier vertices are stored in a priority queue, from which the next closest vertex is repeatedly extracted. The frontier in Dijkstra's algorithm can be as large as "n", the number of vertices. Extracting one of these vertices at a time causes an overhead of log(n) per operation, and thus n log(n) time in total.
"Our new algorithm recursively shrinks the size of the frontier being considered by mixing Dijkstra's and another textbook algorithm, called Bellman-Ford, along with a cleverly designed data structure that allows insertion and extraction in groups," explains Xinkai Shu, a postdoctoral researcher in the "Algorithms and Complexity" department at the Max Planck Institute for Informatics in Saarbrücken, led by Prof. Danupon Nanongkai. As a result, the total number of operations can be reduced significantly, leading to improvements in running time making the overall algorithm run faster.
For their work with the title "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths", Xinkai Shu and his co-authors Ran Duan, Jiayi Mao, and Longshui Yin (all from Tsinghua University, Beijing) as well as Xiao Mao (Stanford University) were awarded a Best Paper Award at the "ACM Symposium on Theory of Computing (STOC)" 2025, one of the leading conferences in theoretical computer science. The award specifically honors contributions that introduce a strong new technique, solve a long-standing open problem, or identify and solve an important new problem. It will be awarded during the conference onJune 23rd in Prague.
Original publication:
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (2025): „Breaking the Sorting Barrier for Directed Single-Source Shortest Paths“. 57th Annual ACM Symposium on Theory of Computing (STOC).
Editor and contact:
Philipp Zapf-Schramm
Max Planck Institute for Informatics
Phone: +49 681 9325 5409
Email: pzs@mpi-inf.mpg.de