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
4
-
Did he asked you about shortest path? Then your a right. Read here stackoverflow.com/questions/10254542/…. But maybe he means the fastest path?– CybercartelCommented Dec 30, 2012 at 14:33
-
Did you take a look at this thread? stackoverflow.com/questions/430142/…– IndexCommented Dec 30, 2012 at 14:36
-
Sorry I didn't look at that thread.– blacktornadoCommented Dec 30, 2012 at 14:46
-
You can read this google blog googleblog.blogspot.com.br/2007/11/… and this great answer: stackoverflow.com/a/432854/2516160– jeanCommented Mar 23, 2015 at 19:36
Add a comment
|
2 Answers
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.
What about A*? It seems suitable for path finding.
answered Jan 9, 2015 at 9:20
