Chinese researchers just wrote the first real improvement to Dijkstra

Chinese researchers just wrote the first real improvement to Dijkstra in 41 years

Dijkstra’s algorithm has been the undefeated king of the shortest path for more than four decades.

Whether you are using a map, booking a flight, or routing a packet across the internet, some version of Dijkstra is usually the engine in the background.

Since 1984, textbooks have treated its efficiency as settled. Fredman and Tarjan showed that, with Fibonacci heaps, you can solve single-source shortest paths in $O(m + n \log n)$. After that, the field hit a wall that became known as the sorting barrier.

To find the shortest path the Dijkstra way, you keep vertices ordered by distance. Sorting has a mathematical floor. For a long time, most people assumed you could not cross it.

Until now.

A team led by Ran Duan at Tsinghua University, with Jiayi Mao, Xiao Mao (Stanford), Xinkai Shu (Max Planck Institute for Informatics), and Longhui Yin, published Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. The paper won Best Paper at STOC 2025.⁠

They proved that Dijkstra is not optimal for the thing we actually want: the distances themselves.

The trick is to stop insisting on a total order. The algorithm mixes Bellman–Ford-style batched relaxations with a recursive partial-ordering scheme (their BMSSP procedure). It works on the frontier in clusters and pivots instead of always extracting the global minimum. You still get correct distances. You do not pay the full sorting tax.⁠

The result is a genuine shift in theoretical computer science:

• The first deterministic improvement to directed SSSP with real non-negative weights since the 1984 bound.
• Time complexity $O(m \log^{2/3} n)$ in the comparison-addition model, beating $O(m + n \log n)$ on sparse graphs.
• On huge sparse networks — the web, logistics graphs, knowledge graphs, road maps — the asymptotic gap is no longer zero.

Last year, work associated with Robert Tarjan showed that Dijkstra is universally optimal if you also require the vertices sorted by distance. That result still stands. Tsinghua’s answer is sharper: if you only need the lengths, stop sorting. Tarjan himself called the attempt audacious. It worked.⁠

Two footnotes, because they matter.

First, this is a theoretical breakthrough, not a drop-in replacement for production routers tomorrow. Early implementations still lose to a well-tuned Dijkstra on graphs of practical size; the constants are large. That is normal. The 1984 bound also took years to become the default mental model.

Second, the door did not close in 2025. In early 2026 the same circle of authors already published a faster deterministic bound, roughly $O(m\sqrt{\log n})$​ on sufficiently dense instances. Once a 40-year wall cracks, the next papers arrive quickly.

Paper: arXiv:2504.17033

For four decades the greatest minds in algorithms treated this limit as part of the furniture. It was not. If a settled law in basic graph theory can move, other “impossible” speed limits are worth looking at again — in routing, in compilers, in the graphs that sit underneath agents and local models.

At GeneForge we care about foundations that still move. Textbooks are a starting point, not a ceiling.