Speaking of GraphHopper, a fast Open Source route planner based on OpenStreetMap, I have read a bit literature and implemented some methods. The simplest solution is a Dijkstra and a simple improvement is a bidirectional Dijkstra which explores roughly only the half of the nodes. With bidirctional Dijkstra a route through entire Germany takes already 1sec (for car mode), in C it would be probably only 0.5s or so ;)

I've created an animated gif of a real path search with bidirectional Dijkstra here. Also there are some more ideas to make Dijkstra faster like doing A*, which is a "goal-oriented Dijkstra". Also I've create a gif-animation for it.

But how to do it (a lot) faster?

The problem is that for a path search all nodes between the locations have to be explored and this is really costly as already in Germany there are several millions of them. But an additional pain point of Dijkstra etc is that such searches uses lots of RAM.

There are heuristic solutions but also exact solutions which organzize the graph (road network) in hierarchical layers, both have pro&cons and mainly solve the speed and RAM problem. I've listed some of them in this answer.

For GraphHopper I decided to use Contraction Hierarchies because it is relative 'easy' to implement and does not take ages for preparation of the graph. It still results in very fast response times like you can test at our online instance GraphHopper Maps. E.g. from south Africa to east China which results in a 23000km distance and nearly 14 days driving time for car and took only ~0.1s on the server.

Speaking of GraphHopper, a fast Open Source route planner based on OpenStreetMap, I have read a bit literature and implemented some methods. The simplest solution is a Dijkstra and a simple improvement is a bidirectional Dijkstra which explores roughly only the half of the nodes. With bidirctional Dijkstra a route through entire Germany takes already 1sec (for car mode), in C it would be probably only 0.5s or so ;)

I've created an animated gif of a real path search with bidirectional Dijkstra here. Also there are some more ideas to make Dijkstra faster like doing A*, which is a "goal-oriented Dijkstra". Also I've create a gif-animation for it.

But how to do it (a lot) faster?

The problem is that for a path search all nodes between the locations have to be explored and this is really costly as already in Germany there are several millions of them. But an additional pain point of Dijkstra etc is that such searches uses lots of RAM.

There are heuristic solutions but also exact solutions which organzize the graph (road network) in hierarchical layers, both have pro&cons and mainly solve the speed and RAM problem. I've listed some of them in this answer.

For GraphHopper I decided to use Contraction Hierarchies because it is relative 'easy' to implement and does not take ages for preparation of the graph. It still results in very fast response times like you can test at our online instance GraphHopper Maps. E.g. from south Africa to east China which results in a 23000km distance and nearly 14 days driving time for car and took only ~0.1s on the server.