Revision as of 12:45, 1 June 2025 edit The Anome (talk \| contribs) Edit filter managers, Administrators 260,102 edits →An interesting paper questioning optimality: clarify Tag: 2017 wikitext editor ← Previous edit		Revision as of 12:46, 1 June 2025 edit undo The Anome (talk \| contribs) Edit filter managers, Administrators 260,102 edits →An interesting paper questioning optimality: maithing it properly Tag: 2017 wikitext editor Next edit →
Line 73: claims better-than-Dijkstra asymptotic performance in some edge cases. 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." — [[User:The Anome\|The Anome]] ([[User talk:The Anome\|talk]]) 12:43, 1 June 2025 (UTC)

Talk:Dijkstra's algorithm: Difference between revisions