This paper demonstrates that Dijkstra’s shortest-path algorithm is universally optimal when used in conjunction with an efficient heap data structure, ensuring optimal performance for every graph topology. A new heap data structure with a working-set property is introduced, reducing the cost of extracting the minimum element to merely logarithmic in the number of inserted elements, rather than all elements in the heap. This unique property makes the extraction of recently added elements more cost-effective. The working-set property guarantees universal optimality, particularly in ordering vertices by their distance from the source vertex. This research presents groundbreaking results in the efficiency of graph algorithms.
https://arxiv.org/abs/2311.11793