Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 12:44, 1 June 2025

Latest revision as of 12:57, 1 June 2025

(5 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 73:

claims better-than-Dijkstra asymptotic performance in some edge cases.

The abstract reads as follows: "We give a deterministic <math>O(m log2\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]].

&mdash; [[User:The Anome|The Anome]] ([[User talk:The Anome|talk]]) 12:43, 1 June 2025 (UTC)