Breaking through the 40-year bottleneck of Dijkstra's algorithm, Tsinghua professors and others have overturned the textbook and won the best paper at STOC.

Professor Duan Ran from Tsinghua University has proposed a new method for finding the shortest path, outperforming the classic Dijkstra's algorithm in textbooks.

A significant achievement in computer science!

A professor from Tsinghua University has refreshed the understanding of the shortest path algorithm and may rewrite the computer algorithm textbooks.

In computer science, a classic problem is to find the shortest path from each point in a network. Dijkstra's algorithm is the most classic solution to this problem.

Since 1956, the shortest path problem has attracted the attention of many researchers.

Mikkel Thorup, a computer scientist from the University of Copenhagen, said:

The shortest path is an excellent problem that people around the world can relate to.

Intuitively, finding the path to the nearest point from the starting point should be the simplest.

Therefore, if you want to design the fastest algorithm to solve the shortest path problem, a reasonable approach is to first find the nearest point, then the second - nearest point, and so on. But this means you need to repeatedly determine which point is the nearest, that is, you have to sort these points by distance.

However, this method has a fundamental limitation: This algorithm cannot be faster than the time required for sorting.

Forty years ago, scientists researching shortest path algorithms encountered this "sorting bottleneck".

Now, a research team from institutions including Tsinghua University has designed a new algorithm that breaks through this bottleneck. This algorithm does not rely on sorting and runs faster than any algorithm that requires sorting.

Paper link: https://arxiv.org/abs/2504.17033

Robert Tarjan, a computer scientist from Princeton University, said: "These researchers boldly believed that they could break through this bottleneck. This is an amazing result."

It is worth mentioning that this research won the best paper at STOC, which is well - deserved.

Left: Mikkel Thorup; Right: Robert Tarjan

The Shortest Path

If you want to solve complex problems, being well - organized often yields twice the result with half the effort. For example, break the problem down and prioritize the simplest parts first - but this kind of classification comes at a cost. You may spend too much time on sorting.

This dilemma is especially evident in one of the most classic problems in computer science: How to find the shortest path from a specific starting point to all other points in a network. This is like an upgraded version of the problem you must solve after moving house: planning the best routes from your new home to work, the gym, and the supermarket.

To analyze the shortest path problem from a mathematical perspective, researchers use the language of graph theory - a graph is a network composed of points (or nodes) connected by lines. Each connecting line is marked with a number called the weight, which can represent the length of the line or the time required to traverse it.

Usually, there are many paths between any two nodes. The shortest path is the one with the smallest sum of weights. Given a graph and a specific "starting point", the goal of the algorithm is to find the shortest path to each other node.

In 1956, computer science pioneer Edsger Dijkstra designed the most famous shortest path algorithm.

It starts from the starting point and expands step by step.

How Dijkstra's Algorithm Finds the Shortest Path

Dijkstra's algorithm starts from a specific point in the network and finds the shortest path to each other point. It finds these paths in order of increasing distance.

The basic steps of Dijkstra's algorithm:

Start from point A:

You see two paths. Point B is 1 unit away, and point C is 5 units away. You now know the shortest path to B, but there may be a shorter indirect path to C. Shortest path: A → B = 1

Follow the shortest path:

Go to B, then observe again and record the total distance from A to each point. Point D is closer to A than point C. Shortest path: A → B = 1; A → D = 2

Continue exploring:

Go to point D and observe again. Now you have found the shortest path to C. Shortest path: A → B = 1; A → D = 2; A → C = 3.

Starting from the starting point and gradually exploring the shortest path to each point in the network - this method is effective because knowing the shortest path to nearby nodes can help you find the shortest path to farther nodes.

But the final result is a list of shortest paths sorted by distance. Therefore, the sorting bottleneck sets a fundamental limit on the speed of the algorithm.

In 1984, Tarjan and another researcher improved Dijkstra's original algorithm to reach this speed limit. Any further improvement must come from an algorithm that avoids sorting.

Paper link: https://dl.acm.org/doi/10.1145/28869.28874

In the late 1990s and early 2000s, Thorup and other researchers designed algorithms that broke through the sorting bottleneck.

From left to right: Bernhard Haeupler, Václav Rozhoň (above), Jakub Tětek (below), Robert Tarjan, and Richard Hladík proved that a version of Dijkstra's algorithm is the best solution for all network layouts

They need to make certain assumptions about the weights. No one knows how to extend these techniques to arbitrary weights. It seems that they have reached the end.

Research stagnated for a long time, and many people believed that there was no better way.

But Duan Ran from Tsinghua University is not one of them. He has long dreamed of constructing a shortest path algorithm that can break through the sorting bottleneck on all graphs. Last autumn, he finally succeeded.

Beyond Sorting

Duan Ran's attention to the sorting bottleneck can be traced back nearly 20 years.

At that time, he was a graduate student at the University of Michigan. His supervisor was one of the scholars researching how to break through the sorting bottleneck in specific situations.

But it wasn't until 2021 that Duan Ran found a more promising method.

The key lies in focusing on the next step of each step of the algorithm.

Dijkstra's algorithm uses the previously explored area to decide the next step by scanning the "boundary" of this area - that is, all nodes connected to the boundary. Initially, this doesn't take much time, but as the algorithm progresses, the speed slows down.

Duan Ran envisioned grouping adjacent nodes on the boundary into multiple clusters. Only one node in each cluster is considered at each step. Since the number of nodes to be screened is reduced, each step of the search can be faster. The algorithm may not always choose the nearest node, so the sorting bottleneck no longer applies. But ensuring that this cluster - based method actually speeds up the algorithm rather than slowing it down is a challenge.

In the following year, Duan Ran refined this basic idea.

By the autumn of 2022, he was optimistic that he could overcome the technical difficulties.

He recruited three graduate students to help refine the details. A few months later, they achieved partial success - developing an algorithm that breaks through the sorting bottleneck for arbitrary weights, but only applicable to so - called undirected graphs.

Paper link: https://arxiv.org/abs/2307.04139

In an undirected graph, each connecting line can be traversed in both directions. Computer scientists usually pay more attention to the more general class of graphs containing one - way paths, but these "directed graphs" are often more difficult to handle.

Mao Xiao, a doctoral student in computer science at Stanford University and a co - author of the new paper, said: "In a directed graph, there may be a situation where it is easy to go from A to B, but difficult to go from B to A. This can cause you a lot of trouble."

The Road of Hope

In the summer of 2023, at an academic conference in California, Mao Xiao listened to Duan Ran's speech on the undirected graph algorithm. He took the initiative to talk to this scholar he had admired for a long time.

It was the first time he met Duan Ran in person, and he was very excited at that time.

How Randomness Optimizes the Algorithm

After the conference, Mao Xiao began to think about this problem in his spare time. Meanwhile, Duan and his team were exploring new methods applicable to directed graphs. They drew inspiration from another classic algorithm for the shortest path problem - the Bellman - Ford algorithm.

The Bellman - Ford algorithm does not generate a sorted list, but at first glance, it seems like a bad choice: it is much slower than Dijkstra's algorithm.

Computer scientist Mikkel Thorup added: "Scientific research is about constantly trying potential paths. But borrowing from the Bellman - Ford algorithm is like going against the grain - it seems really stupid."

Duan Ran's team avoided the slow - speed defect of the Bellman - Ford algorithm by running it in stages. This selective use allows them to pre - scout the most valuable nodes in subsequent steps, and these nodes are like the core hubs in a transportation network.

Computer scientist Mikkel Thorup explained: "To obtain the shortest paths to most destinations, you must pass through these key points."

In March 2024, Mao Xiao proposed another innovative idea.

Some key steps in the original algorithm rely on randomness. Although random algorithms can efficiently solve many problems, the academic community still prefers deterministic solutions.

Mao Xiao designed a method to solve the shortest path problem without randomization and then joined the team.

After months of group chats and video conferences, they finally made a breakthrough in the autumn - Professor Duan Ran realized that he could borrow the technique he used to break through the sorting obstacle when solving another type of graph problem in 2018. This was