Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps

Our paper with Bernhard Haeupler, Václav Rozhoň, Robert E. Tarjan and Jakub Tětek about how certain implementations of Dijkstra are in some sense optimal on every graph, if one uses a nice enough heap.