But that statement doesn't apply to the version of Dijkstra's developed in this paper right?
> Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology.
It clarifies specifically what problem it is optimal for "We prove that our working-set property is sufficient to guarantee universal optimality, specifically, for the problem of ordering vertices by their distance from the source vertex", but A* only explores a subset of vertices based on the heuristic, so it can be more efficient.
> But that statement doesn't apply to the version of Dijkstra's developed in this paper right?
Simple thought experiment: I have an algorithm that has path costs for one graph memorized and first compares to that graph; it's O(V+E) to compare and return the value for that memorized graph. It obviously beats this algorithm for that graph.