Universal optimality of Dijkstra via beyond-worst-case heaps

> When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's.

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.

Does google maps use something like this? I imagine all pairs is too expensive, but the topology should be fairly consistent over time

TDH seems like it would tend to coincidentally reproduce the tendency of animals (humans included) to create paths by having lots of people travel through somewhere. The cause and effect is flipped, but the player doesn’t have to know that, right?

FYI, TDH sounds like what Skyrim or one of the previous games uses.

I can't remeber exactly, but $thing was supposed to be hard to find, but because of how they baked in pathing costs- if you followed something it'd lead you there.

It took me a few minutes before I realized that putting “n” at the end of “prove” makes the HN title readable.

But yeah, should have just used the original title.

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).

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.

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.

I had him as a teaching assistant when I was teaching data structures at Princeton back in Fall 2013. Princeton CS has their professors rotate through as TAs every so often through their courses.

That semester, I made a slight mistake on the final exam where I asked students to create an algorithm that could find the second shortest path from s to every other vertex in a graph. I forgot to specify that the second shortest path should be simple (i.e. should not reuse any vertex twice). Having to deal with non-simple paths makes the problem much much harder.

None of the students figured it out in the time available, and I'm sure I would also have been stumped if I had tried to solve the problem. Bob figured it out though. And then I remember he graded all 150 solutions to the problem himself, having as a blast as he went through students attempts at an effectively impossible problem.

There's a notable exception:

>when combined with a sufficiently efficient heap data structure

So it depends on the circumstances a bit.

A* is faster in practice if the heuristics used by the specific implementation are accurate and if the graph is "general" for the problem space. I'm being very loose with the word "general" but essentially it should have typical structure for the problem space it represents.

There's almost certainly a paper somewhere proving that A* with a given heuristic can always be made O(large) by choosing the right adversarial inputs.

I think A* is solving a different problem than dijkstra's, since it requires an admissible heuristic to do any better than dijkstra's.

As long as you have an admissible heurustic, A* won't ever perform worse than dijkstra's.

The two algorithms solve different (but related) problems. A* finds the shortest path from a source to a single target node. Dijkstra's finds the shortest paths from a source to all other nodes. If you're using Dijkstra's as a search algorithm then it may be slower than A* (often will be, but it depends on the heuristic), but you'll be terminating the algorithm early (once your target has been found you don't need to continue the algorithm).

The algorithm under discussion is not that search-use of Dijkstra's, but the original all shortest paths use, so it's not directly comparable here to A*.

A* with a consistent heuristic is Dijkstra on a modified graph whose edge weights are the original edge weights plus f(target) - f(source) where f is the A* "heuristic".

If the heuristic is not consistent, the edge weights aren't necessarily nonnegative, but you can still use the "hybrid Bellman–Ford–Dijkstra algorithm", which is a generalization of Dijkstra that works for all graphs, and should be asymptotically better than naive A*.

Others pointed that A* and Dijkstra's algorithm solve different problems. But there's another possibility: less general but more efficient algorithm. For example, there are faster algorithms for planar graphs.

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).

The paper studies "... the problem of ordering vertices by their distance from the source vertex."

If all you need is shortest path between just one pair of points, this result doesn't necessarily apply.

That's wrong, A* can trivially handle a set of points at one end (you might have to "reverse" the direction depending on which end has the set).

Several other commenters have now pointed out the differentiations, in case you weren't aware.