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/RPNTZTJE...
_______________________________________________ NANOG mailing list
https://lists.nanog.org/archives/list/nanog@lists.nanog.org/message/X56R5NAP...