Talk:Dijkstra's algorithm: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Add topic

Revision as of 12:48, 1 June 2025 edit The Anome (talk \| contribs) Edit filter managers, Administrators 260,102 edits →An interesting paper questioning optimality: How this relates to the earlier claims of proof of universal optimality, I don't know. Tag: 2017 wikitext editor ← Previous edit		Latest revision as of 12:57, 1 June 2025 edit undo The Anome (talk \| contribs) Edit filter managers, Administrators 260,102 edits →An interesting paper questioning optimality: It will be interesting to see if this gets out of pre-print status into WP:RS. Tag: 2017 wikitext editor
(2 intermediate revisions by the same user not shown)
Line 67: == An interesting paper questioning optimality == This paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths": ~~This paper:~~ https://arxiv.org/abs/2504.17033 Line 75: The abstract reads as follows: "We give a deterministic <math>O(m\log^{2/3}n)</math>-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the <math>O(m+n\log n)</math> time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP." ~~How~~They ~~this relates to~~cite the earlier ~~claims~~work ofon proof of universal optimality, Iand ~~don~~state that Dijkstra'ts algorithm is still optimal ''if you want to know the order of the points in the path''; their algorithm does not produce this ordering. It will be interesting to see if this gets out of pre-print status into [[WP:RS]]. — [[User:The Anome\|The Anome]] ([[User talk:The Anome\|talk]]) 12:43, 1 June 2025 (UTC)