Content deleted Content added
m Archiving 2 discussion(s) to Talk:Dijkstra's algorithm/Archive 2) (bot |
→An interesting paper questioning optimality: It will be interesting to see if this gets out of pre-print status into WP:RS. |
||
| (7 intermediate revisions by the same user not shown) | |||
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 questioning optimality ==
This paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths":
https://arxiv.org/abs/2504.17033
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."
They cite the earlier work on proof of universal optimality, and state that Dijkstra's 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)
| |||