Fastest Routing Algorithm Ever

It's called Contraction Hierarchies and it's so awesome.

Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks.

This paper is 70 pages ... note that there is another paper that has exactly the same title, but is only 15 pages. The latter is pretty much incomprehensible so make sure to only use the long version.

Oh and the same group of German researchers has come up with even faster algorithms, but I think they all use Contraction Hierarchies as a starting point. Dominik Schultes (et al?) made an older algorithm called Highway Hierarchies, but I have the impression Contraction Hierarchies makes it obsolete.

How awesome are Contraction Hierarchies? They're so fast that (assuming you use plain CHs with no further optimizations) it may take longer merely to enumerate (traverse) the shortest path than to find it in the first place! This is possible because CH uses "shortcuts" that skip past most of the individual road segments on the route on the way to the destination.

Important update: there are a couple of things the inventors will not tell you about CHs.

First, although you may have only 100 nodes settled in a CH search compared to 100,000 in a normal highway graph, the fan-out of each node is greater, and there is a performance penalty for that. On the whole it is very fast, but I'm just telling you that while the inventors like to tout the nodes settled ratio (100,000/100), it doesn't reflect the speedup you're actually going to get. Especially not if you're already using heuristics to avoid searching the whole graph.

Second, and more importantly, real-world street-network routing requires a node for every street segment, and an edge for each transition from one road segment to another. This is necessary to model turn restrictions (and turn costs), as there is no other known way to support them. In street networks, this typically makes the graph about 3 times larger (in terms of the number of nodes and edges) than the graphs that the inventors usually operate on (which have a node for each intersection, and an edge for each road). They did make a paper explaining this, "Route Planning in Road Networks with Turn Costs"; however the paper does not explain the performance penalty for using this kind of network. You might think because the network is 3 times larger that it will be 3 times slower, and I assumed as much. However, I found out after implementing a whole system based on this kind of road network that CHs actually perform about 30 times slower, not 3 times slower.

This second problem actually made CHs too slow for large road networks on our mobile devices. When we used Dijkstra's algorithm we could present a partial solution to the user after 5 seconds (a "best guess" about the first few turns the user should make), but a CH does not provide partial solutions nor guesses--in general, you must wait for a unique solution before reporting the first turn instruction. You can present a turn instruction before fully unpacking the route, but in a road network with turn costs, the initial search takes more time than the unpacking. Thus, in the real world CHs are only suitable for faster machines (let's say 800MHz), unless your code is carefully optimized for the specific task of dealing with the CH (unlike my code, which fit the CH into general purpose data structures that were also used by the rest of the system, yielding compute times of 30+ seconds, not including route unpacking).