> 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?
A sibling post answers your question, but I found your quote interesting for a different reason: This working set property seems like something that would be very useful in practice for quite a few problems, even if it can't be pushed all the way to proving universal optimality. We often have some freedom in choosing what order to supply inputs to a problem we're trying to solve; if we can order things so that, 99% of the time, the minimum item that we're looking for turns out to be within the last 1000 items considered instead of the complete set of 1000000, that's a nearly 10x constant factor speed up right there.
Well not exactly because it’s the log of the number. So it’s log 1000 vs log 1000000 which is a much smaller difference.
Also if you actually know the minimum item it’s much better for it to be first because it means you can skip almost all the work. The paper is focused on doing the best for a worst case input. In real life if you can guess you can improve the average case substantially. For example, this is what A* tries to do.
Too late to edit so I'll self- reply: My claim was completely wrong, log 1000 is only about half of log 1000000, and this is true regardless of base. Whoops...
Yes. If your distances are dense integers, you can use a simple array as the priority queue in Dijkstra, and it will be faster than a heap (Dial’s algorithm).
You can use a radix heap rather than a binary heap. I have an implementation here, with benchmarks using pathfinding: https://github.com/mpdn/radix-heap
It has the nice property that the amortized cost of pushing/popping an element is independent of the number of other elements in the heap.
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?