A New Algorithm Makes It Faster to Find the Shortest Paths

Abstraction: New algorithm breaks 40-year sorting barrier for shortest-path problems

Key points:

• Dijkstra's 1956 algorithm improved by Tarjan in 1984 to hit the "sorting barrier" — a fundamental speed limit for any algorithm that processes nodes in distance order
• Ran Duan (Tsinghua) and collaborators devised an algorithm that breaks the sorting barrier for arbitrary-weight directed and undirected graphs (arXiv:2504.17033)
• Key insight: cluster frontier nodes to avoid processing every node in sorted order, then use selective Bellman-Ford steps to scout high-value "thoroughfare" nodes
• Earlier work (late 1990s–2000s) broke the barrier only under restricted weight assumptions; Duan's approach generalizes to all weights
• Xiao Mao (Stanford) contributed a derandomized version; techniques from a 2018 Duan paper on a different graph problem provided the final piece
• "This thing might as well have been discovered 50 years ago, but it wasn't" — Thorup; algorithm relies on no fancy mathematics, making the result more striking

Connections: Ran Duan · Robert Tarjan · Graph Algorithms · Computational Complexity

Source: https://www.wired.com/story/new-method-is-the-fastest-way-to-find-the-best-routes/