Chinese researchers have developed the best shortest-path algorithm in 41 years.
Dijkstra’s Algorithm has been the undefeated king of the shortest path for over 40 years.
Whether you’re using Google Maps, booking a flight, or routing internet packets, Dijkstra is the engine running in the background.
Since 1984, textbooks have taught that its efficiency was hit by a “sorting barrier.”
To find the shortest path, you have to sort the points by distance. And sorting has a mathematical floor you can’t cross.
Until now.
A research team from Tsinghua University just published a paper that shatters the 41-year-old record.
They proved that Dijkstra is not optimal.
By combining the logic of the Bellman-Ford algorithm with a revolutionary “recursive partial ordering” method, they figured out how to find the path without fully sorting the nodes.
The results are a massive shift in theoretical computer science:
- the first deterministic improvement to the Single-Source Shortest Path (SSSP) problem since 1984
- a new time complexity of O(m log^(2/3) n), officially beating the long-standing O(m + n log n) limit
- on massive sparse graphs (like the web or global logistics), this means finding the best route significantly faster than previously thought possible
For four decades, the greatest minds in algorithms believed this limit was absolute.
Last year, even the legendary Robert Tarjan won an award proving Dijkstra was “optimally efficient” at sorting distances.
Tsinghua’s answer? Stop sorting.
The world’s most settled problem is suddenly wide open again.
If we can break a 40-year-old law in basic graph theory, what other “impossible” speed limits are waiting to be crushed?
원문: https://x.com/kyronis_talks/status/2053770788210405618?s=52