TLDR: Dijkstra got defeated after 40 years. It will be interesting to see what convergence times will look like with this implemented.
Good case study of why you can't TLDR science. From the paper directly , emphasis on the last sentence mine : Dijkstra’s algorithm also produces an ordering of vertices by distances
from the source as a byproduct. A recent contribution by Haeupler, Hladík, Rozhoň, Tarjan and Tětek [HHR+24] showed that Dijkstra’s algorithm is optimal if we require the algorithm to output the order of vertices by distances. If only the distances and not the ordering are required, a recent result by Duan, Mao, Shu and Yin [DMSY23] provided an O(m √ log n log log n)-time randomized SSSP algorithm for undirected graphs, better than O(n log n) in sparse graphs. ***** However it remains to break such a sorting barrier in directed graphs. *****
1. Dijkstra wasn't 'defeated'. There have been many algorithms that outperformed Dijkstra's under specific cases. 2. OSPF and IS-IS are directed graphs. This algorithm outperforms Dijkstra on *undirected* graphs. On Sun, Aug 17, 2025 at 11:57 PM Ryan Hamel via NANOG <nanog@lists.nanog.org> wrote:
I was scrolling LinkedIn and came across a post that mentioned a research paper: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
TLDR: Dijkstra got defeated after 40 years. It will be interesting to see what convergence times will look like with this implemented.
Different formats of the same research paper:
* https://arxiv.org/pdf/2504.17033 * https://dl.acm.org/doi/pdf/10.1145/3717823.3718179
Kind regards,
Ryan Hamel
_______________________________________________ NANOG mailing list
https://lists.nanog.org/archives/list/nanog@lists.nanog.org/message/RPNTZTJE...