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

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

Mea culpa here. Tom Strickx pointed out to me that I misread part of the
intro. I incorrectly assumed that the DMSY23 algorithm (which does not beat
Dijkstra on directed ) was the subject of the paper. It is not, that was
prior work by the same authors.

The paper does make the claim that their new algo beats Dijkstra on
directed, and I wanted to make sure I wasn't promulgating false info from
my mistake.

Saku's point with respect to materiality is still applicable though.
Especially that flooding takes way more time than SPF.

On Mon, Aug 18, 2025 at 10:26 AM Tom Beecher <beecher () beecher cc> wrote:

> 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/3HRCGCDV6L7WCRLTZ6ZGZYV5ENT4WOYD/