Someone found a faster algorithm than Dijkstra's after 69 years. And that's absolutely wild.

Time to drop some graph theory lore.

Dijkstra invented his single-source shortest-path algorithm in 1956, and it is remarkable for how long it has stood as the best deterministic algorithm for this problem. Since then, the only improvements have come from tweaking the priority queue, culminating with Fibonacci heaps in the 1980's, yielding a runtime of O(E + V log V).

And then, out of nowhere, a new 2025 paper, "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths" (by Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin) comes out with a new O(E * (log V)^0.67)-time algorithm. This beats Dijkstra for sparse graphs.

To see how crazy that is, compare it with the table below, which shows the slow, gradual improvements for another classic graph problem: the Minimum Spanning Tree (MST) problem.

Dijkstra's reign lasted so long that it was widely believed to be optimal. In fact, if I read between the lines, it seems that the legendary Robert E Tarjan (co-inventor of the Fibonacci heap mentioned above, and who is all over the MST table below) has recently been trying to prove that Dijkstra's algorithm is truly optimal. Two of his most recent papers, "Bidirectional Dijkstra's Algorithm is Instance-Optimal" (2024) and "Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps" (2023), chip away at showing how Dijkstra is optimal in different aspects, almost--but not quite--precluding the new result!

1956-2025. What a run.

Credits:
- The paper: arxiv.org/pdf/2504.17033
- The screenshot is from basics.sjtu.edu.cn/~liguoqiang/teaching/EI6303/lectures/algo3.pdf
- Thanks to Dima Korolev for telling me about the new result!

Fun facts:
- Two of the authors have a background in competitive programming: codeforces.com/blog/entry/143462
- The best possible deterministic runtimes, for both single-source shortest-paths and for MST, remain a mystery.