Comment by mvkg

The paper's claim for Dijkstra's is it's "a single algorithm performs as well as possible for every single graph topology". A* is an augmented version of Dijkstra's only applicable when there is a priori knowledge of a good heuristic for the topology (e.g. manhattan distance in a cartesian plane). Since there is almost certainly no heuristic that is universally optimal for all topologies, A* shouldn't be more universally optimal than Dijkstra's (and can probably perform worse given a bad heuristic).