Revision as of 12:43, 1 June 2025 edit The Anome (talk \| contribs) Edit filter managers, Administrators 260,102 edits An interesting paper (2025) Tag: 2017 wikitext editor ← Previous edit		Revision as of 12:44, 1 June 2025 edit undo The Anome (talk \| contribs) Edit filter managers, Administrators 260,102 edits →An interesting paper (2025): more Tag: 2017 wikitext editor Next edit →
Line 66: https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=1261954063 [[Special:Contributions/82.218.89.72\|82.218.89.72]] ([[User talk:82.218.89.72\|talk]]) 07:06, 16 December 2024 (UTC) == An interesting paper ~~(2025)~~questioning optimality == This ~~interesting~~ paper: https://arxiv.org/abs/2504.17033 ~~suggests~~claims better-than-Dijkstra asymptotic performance in some edge cases. The abstract reads as follows: "We give a deterministic O(m log2/3 n)-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 O(m + n log n) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP."

Talk:Dijkstra's algorithm: Difference between revisions