In 2023, Haeupler, Rozhoň, Tětek, Hladík, and [[Robert Tarjan|Tarjan]] (one of the inventors of the 1984 heap), proved that, for Dijkstra'sthe shortest-pathproblem algorithmof issorting universallythe (everyvertices graphof [[topology]])a optimalpositively-weighted indirected runninggraph timefrom anda numbergiven ofstarting comparisonsvertex, a whenversion usedof Dijkstra's algorithm with ana efficient-enoughspecial heap data structure. Theydesignedhas a heapruntime and number of comparisons that matchesis thewithin worst-casea boundsconstant factor of Fibonaccioptimal heapsamong andalgorithms providesfor the beyond-worst-casesame guaranteesorting thatproblem 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>
