Revision as of 12:25, 30 May 2025 edit Lowercase sigmabot III (talk \| contribs) Bots, Page movers 2,447,693 edits m Archiving 2 discussion(s) to Talk:Dijkstra's algorithm/Archive 2) (bot ← Previous edit		Revision as of 12:43, 1 June 2025 edit undo The Anome (talk \| contribs) Edit filter managers, Administrators 260,102 edits An interesting paper (2025) Tag: 2017 wikitext editor Next edit →
Line 65: Last good version:<br> 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) == This interesting paper: https://arxiv.org/abs/2504.17033 suggests 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." — [[User:The Anome\|The Anome]] ([[User talk:The Anome\|talk]]) 12:43, 1 June 2025 (UTC)

Talk:Dijkstra's algorithm: Difference between revisions