Algorithm/Method Use By Google Maps For Finding the Path Between Two Cities

Question

Recently I had a job interview they asked me "Which method is use by google maps for finding the shortest path between two cities?". I didn't had the answer to that question but I guessed they use the "Shortest Path Algorithm" for finding the path but the interviewer said "No". After that interview I Googled a lot but didn't find any method for that. Please tell me if you have any idea about how google maps find shortest path between two cities

Answer 1

As it happens I just attended a talk about it. Dijkstras Algorithm is too inefficient for google. Although the complexity, n log n , is fine the absolute time it takes is quite large.

Google uses a variant of Contraction Hierarchies. It is faster than Dijkstra because the network is preprocessed. Even though there are faster algorithms out there that involve preprocessing, CH provides a lot of flexibility.

Answer 2

What about A*? It seems suitable for path finding.