Every time Google Maps gives you directions, your phone does this. 14,671 streets searched to find a single 2.3 km route across Naples. It's called Dijkstra, the undefeated king of shortest path since 1959. Until last month. For 66 years, every GPS, every flight booking, every internet packet route ran on the same algorithm. In 2024, Robert Tarjan and four co-authors won Best Paper at FOCS proving Dijkstra was optimal. The world's most-used algorithm, certified untouchable. Eight months later, a team at Tsinghua led by Ran Duan published a paper proving them wrong. The catch is in what "optimal" means. Tarjan's proof showed Dijkstra is the fastest possible algorithm IF you have to output every point sorted by distance. The Tsinghua group noticed something the field had quietly assumed for 41 years: finding the shortest path does not actually require that sorting. The problem just asks for the distances. They combined Bellman-Ford's batch updates with a recursive partial ordering trick from Duan's own 2023 paper. Instead of sorting the frontier, they cluster the boundary nodes and only explore the representatives. The new bound is O(m log^(2/3) n), beating the 1984 ceiling. Best Paper at STOC 2025. The reframe came before the algorithm. Tarjan did not prove Dijkstra was the best shortest path algorithm. He proved Dijkstra was the best sorted-output shortest path algorithm. The field treated those as the same problem for four decades. They are not. Every speed limit you have memorized has a definition wrapped around it. Crack the definition and the limit breaks. The world's most settled algorithm just got beat by someone asking what problem it was actually solving.
