> > 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 <[email protected]> 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/[email protected]/message/RPNTZTJEGQJ6WMI4AKOFUUOVFP4CP7AC/ > _______________________________________________ NANOG mailing list https://lists.nanog.org/archives/list/[email protected]/message/X56R5NAPCVAR4NSGFLWQ2UZB5ZQT4F5H/
