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

[Saku Ytti via NANOG <nanog () lists nanog org>]

On Mon, 18 Aug 2025 at 06:57, 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.

I don't think it has practical implications for ISIS/OSPF networks, on
a small network with under 300 nodes ISIS SPF costs like 25ms,
flooding takes longer. I'm not sure how much cheaper this is, maybe
I'm butchering this.

If we assume 300 nodes and 900 edges.
irb(main):002:0> (900+300) * Math.log(300) # (the paper claims
𝑂(𝑚+𝑛log 𝑛), while ISIS book by Abe Martey claims O(m log m) or
O(m log n) for non-highly meshed (which is what I used to estimate in
real life with good results, which is somewhat less than what the
paper suggests for Djikstra)
=> 6844.538969587441
irb(main):001:0> 900 * 2/3*Math.log(300)
=> 3422.2694847937205


Absolutely insane improvement, if (doubtful) I'm not butchering this.
But still largely immaterial in practice in this application, but I'm
sure in many other Djikstra applications this kind of win can be
meaningful. I don't understand the paper and can't tell what we are
losing in terms of CPU time needed or DRAM needed, as the improvement
makes assumptions about the environment which may not be true.

-- 
  ++ytti
_______________________________________________
NANOG mailing list 
https://lists.nanog.org/archives/list/nanog () lists nanog org/message/JS5A5VAFI7QCTS6OVVIPGNKHCC6EWKNA/