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

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

> You stopped reading too soon.  ;-P
>
> This paper does indeed work on directed graphs; the paragraph you cited
> was laying down previous work upon which this paper builds.

Sorry Matt, just seeing that you called this out as well. Apparently Gmail
thought you were a dirty spammer. :)

On Mon, Aug 18, 2025 at 2:22 PM Matthew Petach <mpetach () netflight com>
wrote:

> You stopped reading too soon.  ;-P
>
> This paper does indeed work on directed graphs; the paragraph you cited
> was laying down previous work upon which this paper builds.
>
> However, the weakness in this paper lies further down in the heart of it
> on page 4:
>
>
> Total order of Paths. Like in many papers on shortest path algorithms, we
> make the following assumption
> for an easier presentation of our algorithm:
> Assumption 2.1. All paths we obtain in this algorithm have different
> lengths.
>
>
> I don't know of many networks that choose link costs to ensure resulting
> uniqueness of the cumulative cost through the path.  Indeed, ECMP is taken
> to be an assumption for most IGPs we use in the real world.
>
> It's a cute paper, and reading through the algorithms presented, it takes
> an interesting hybrid approach to identifying 'pivot' vertices that are
> more interesting to explore first to speed up pruning of uninteresting
> edges; but it relies on the assumption given above that all paths have
> different lengths so you can unambiguously prune vertices that are greater
> than the current best path length.  In our highly-ECMP-dependent networks,
> that assumption falls flat on its face, and the pruning step fails.
>
> Note further that the data structure proposed in Lemma 3.3 at the bottom
> of page 6 makes the assumption explicit, that updating the structure
> involves only a single insertion or update at each iteration because path
> lengths are unique, so trying to relax the uniqueness assumption would
> involve tossing out their insertion-efficient storage structure as well.
>
> Interesting, but not really currently applicable to modern IP networks.
>
> Unlike what another old-timer might sometimes say, I do *not* encourage my
> competitors to implement this algorithm in their routing hardware.  ;-P
>
> Matt
>
>
>
> On Mon, Aug 18, 2025, 07:27 Tom Beecher via NANOG <nanog () lists nanog org>
> 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/X56R5NAPCVAR4NSGFLWQ2UZB5ZQT4F5H/
_______________________________________________
NANOG mailing list 
https://lists.nanog.org/archives/list/nanog () lists nanog org/message/DEU3HWVSF323SZLTJOCFZDSOSTEQCDCP/