Fetching the paper…
Reading the bibliography…
In this paper we prove that Dijkstra's shortest-path algorithm, if implemented with a sufficiently efficient heap, is universally optimal in its running time, and with suitable small additions is also universally optimal in its number of comparisons.
“Dynamic Optimality Refuted - For Tournament Heaps”
J. Munro, Richard Peng, Sebastian Wild and Lingyi Zhang · 1908
Earlier work this paper cites.
“A note on two problems in connexion with graphs”
Edsger. Dijkstra · 1959
Earlier work this paper cites.
“Algorithm 232: heapsort”
John Williams · 1964
Earlier work this paper cites.
“A Finite Partially Ordered Set and Its Corresponding Set of Permutations”
S.. Kislitsin · 1968
Earlier work this paper cites.
“Object code optimization”
Edward. Lowry and C.. Medlock · 1969
Earlier work this paper cites.
“The theory of parsing, translation, and compiling. 2: Compiling”
Alfred. Aho and Jeffrey. Ullman · 1973
Earlier work this paper cites.
“Finding Dominators in Directed Graphs”
Robert Tarjan · 1974
Earlier work this paper cites.
“Efficiency of a Good But Not Linear Set Union Algorithm”
Robert Tarjan · 1975
Earlier work this paper cites.
“How good is the information theory bound in sorting?”
Michael Fredman · 1976
Earlier work this paper cites.
“Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space”
Peter Van · 1977
Earlier work this paper cites.
“Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract)”
Andrew-Chih Yao · 1977
Earlier work this paper cites.
“A New Data Structure for Representing Sorted Lists”
Scott Huddleston and Kurt Mehlhorn · 1982
Earlier work this paper cites.
“Data structures and network algorithms” 44
Robert Tarjan · 1983
Earlier work this paper cites.
“A Linear-Time Algorithm for a Special Case of Disjoint Set Union”
Harold. Gabow and Robert Tarjan · 1985
Earlier work this paper cites.
“A Linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems”
Dov Harel · 1985
Earlier work this paper cites.
“Self-Adjusting Binary Search Trees”
Daniel Sleator and Robert Tarjan · 1985
Earlier work this paper cites.
“The Pairing Heap: A New Form of Self-Adjusting Heap”
Michael. Fredman, Robert Sedgewick, Daniel Sleator and Robert Tarjan · 1986
Earlier work this paper cites.
“Fibonacci heaps and their uses in improved network optimization algorithms”
Michael. Fredman and Robert Tarjan · 1987
Cited alongside, same era.
“Surpassing the Information Theoretic Bound with Fusion Trees”
Michael. Fredman and Dan. Willard · 1993
Cited alongside, same era.
“Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths”
Michael. Fredman and Dan. Willard · 1994
Cited alongside, same era.
“Priority Queues: Small, Monotone and Trans-dichotomous”
Rajeev Raman · 1996
Cited alongside, same era.
“Recent results on the single-source shortest paths problem”
Rajeev Raman · 1997
Cited alongside, same era.
“Dominators in Linear Time”
Stephen Alstrup, Dov Harel, Peter. Lauridsen and Mikkel Thorup · 1999
Cited alongside, same era.
“A priority queue with the time-finger property”
Amr Elmasry, Arash Farzan and John Iacono · 2012
Later among the works it cites.
“Finding dominators via disjoint set union”
Wojciech Fraczak, Loukas Georgiadis, Andrew Miller and Robert Tarjan · 2013
Later among the works it cites.
“In pursuit of the dynamic optimality conjecture”
John Iacono · 2013
Later among the works it cites.
“Instance-Optimal Geometric Algorithms”
Peyman Afshani, Jérémy Barbay and Timothy. Chan · 2017
Later among the works it cites.
“Hollow Heaps”
Thomas Hansen, Haim Kaplan, Robert. Tarjan and Uri Zwick · 2017
Later among the works it cites.
“An Automatic Inequality Prover and Instance Optimal Identity Testing”
Gregory Valiant and Paul Valiant · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
“Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time”
Mikkel Thorup · 1999
Cited alongside, same era.
“Improved Shortest Paths on the Word RAM”
Torben Hagerup · 2000
Cited alongside, same era.
“Improved Upper Bounds for Pairing Heaps”
John Iacono · 2000
Cited alongside, same era.
“Floats, Integers, and Single Source Shortest Paths”
Mikkel Thorup · 2000
Cited alongside, same era.
“On RAM Priority Queues”
Mikkel Thorup · 2000
Cited alongside, same era.
“Optimal Aggregation Algorithms for Middleware”
Ronald Fagin, Amnon Lotem and Moni Naor · 2001
Cited alongside, same era.
“Beyond the Worst-Case Analysis of Algorithms”
Tim Roughgarden · 2020
Later among the works it cites.
“Universally-optimal distributed algorithms for known topologies”
Bernhard Haeupler, David Wajc and Goran Zuzic · 2021
Later among the works it cites.
“Universally-optimal distributed exact min-cut”
Mohsen Ghaffari and Goran Zuzic · 2022
Later among the works it cites.
“Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality”
Bernhard Haeupler, Harald Räcke and Mohsen Ghaffari · 2022
Later among the works it cites.
“Undirected (1+ ϵ \epsilon )-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms”
Václav Rozhon et al · 2022
Later among the works it cites.
“Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based 𝓁 \mathscr{l} 1 {}_{\mbox{1}} -Oblivious Routing”
Goran Zuzic et al · 2022
Later among the works it cites.
“Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps”
Bernhard Haeupler et al · 2024
Closest in time.
“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”, 2025
Ran Duan et al · 2025
Closest in time.
“Fast and Simple Sorting Using Partial Information”
Bernhard Haeupler et al · 2025
Closest in time.
“Simpler Optimal Sorting from a Directed Acyclic Graph”
Ivor Van, Eva Rotenberg and Daniel Rutschmann · 2025
Closest in time.