Content deleted Content added
→Universal optimality: only optimal for comparison-based algorithms |
|||
Line 170:
Further optimizations for the single-target case include [[Bidirectional search|bidirectional]] variants, goal-directed variants such as the [[A* algorithm]] (see {{slink||Related problems and algorithms}}), graph pruning to determine which nodes are likely to form the middle segment of shortest paths (reach-based routing), and hierarchical decompositions of the input graph that reduce {{math|''s''–''t''}} routing to connecting ''{{mvar|s}}'' and ''{{mvar|t}}'' to their respective "[[Transit Node Routing|transit nodes]]" followed by shortest-path computation between these transit nodes using a "highway".<ref name="speedup2">{{cite conference |last1=Wagner |first1=Dorothea |last2=Willhalm |first2=Thomas |year=2007 |title=Speed-up techniques for shortest-path computations |conference=STACS |pages=23–36}}</ref> Combinations of such techniques may be needed for optimal practical performance on specific problems.<ref>{{cite journal |last1=Bauer |first1=Reinhard |last2=Delling |first2=Daniel |last3=Sanders |first3=Peter |last4=Schieferdecker |first4=Dennis |last5=Schultes |first5=Dominik |last6=Wagner |first6=Dorothea |year=2010 |title=Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm |url=https://publikationen.bibliothek.kit.edu/1000014952 |journal=J. Experimental Algorithmics |volume=15 |pages=2.1 |doi=10.1145/1671970.1671976 |s2cid=1661292}}</ref>
=== Optimality for comparison-sorting by distance ===
As well as simply computing distances and paths, Dijkstra's algorithm can be used to sort vertices 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 [[Comparison sort|comparison-based]] algorithms for the same sorting problem on the same graph. To achieve this, they design a comparison-based 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===
| |||