> Our universal optimality result reveals a surprisingly clean interplay between this property and Dijkstra’s algorithm: Any heap with the working set property enables the algorithm to efficiently leverage every structural attribute of the graph it operates on, to the fullest extent that any comparison-based algorithm possibly can.
That last bit makes me wonder: what would a shortest path algorithm without comparisons look like? Are there also "radix sort" like approaches to shortest-path algorithms that surpass comparison-based algorithms or something?
That last bit makes me wonder: what would a shortest path algorithm without comparisons look like? Are there also "radix sort" like approaches to shortest-path algorithms that surpass comparison-based algorithms or something?