Re: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

[Tom Beecher via NANOG <nanog () lists nanog org>]

> 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/RPNTZTJEGQJ6WMI4AKOFUUOVFP4CP7AC/
_______________________________________________
NANOG mailing list 
https://lists.nanog.org/archives/list/nanog () lists nanog org/message/X56R5NAPCVAR4NSGFLWQ2UZB5ZQT4F5H/