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/RPNTZTJE...