Dijkstra's algorithm: Difference between revisions

Revision as of 07:57, 9 December 2024

Revision as of 07:58, 9 December 2024

Line 171:

=== Universal optimality ===

InAs 2023,well Haeupler,as Rozhoň,simply Tětek,computing Hladík,distances and [[Robert Tarjan|Tarjan]] (one of the inventors of the 1984 heap)paths, provedDijkstra's that,algorithm forcan thebe problemused ofto sorting thesort vertices of a positively-weighted directed graph by their distances from a given starting vertex,.

In 2023, Haeupler, Rozhoň, Tětek, Hladík, and [[Robert Tarjan|Tarjan]] (one of the inventors of the 1984 heap), proved that, for this sorting problem on a positively-weighted directed graph, a version of Dijkstra's algorithm with a special heap data structure has a runtime and number of comparisons that is within a constant factor of optimal among algorithms for the same sorting problem on the same graph. To achieve this, they design a heap whose cost of returning/removing the minimum element from the heap is logarithmic in the number of elements inserted after it rather than in the number of elements in the heap.<ref>{{Citation |last=Haeupler |first=Bernhard |title=Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps |date=2024-10-28 |url=https://arxiv.org/abs/2311.11793 |access-date=2024-12-09 |doi=10.48550/arXiv.2311.11793 |last2=Hladík |first2=Richard |last3=Rozhoň |first3=Václav |last4=Tarjan |first4=Robert |last5=Tětek |first5=Jakub}}</ref><ref>{{Cite web |last=Brubaker |first=Ben |date=2024-10-25 |title=Computer Scientists Establish the Best Way to Traverse a Graph |url=https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/ |access-date=2024-12-09 |website=Quanta Magazine |language=en}}</ref>

===Specialized variants===