4

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

blacktornado
  • 123
  • 1
  • 2
  • 6
  • Did you take a look at this thread? http://stackoverflow.com/questions/430142/what-algorithms-compute-directions-from-point-a-to-point-b-on-a-map – Index Dec 30 '12 at 14:36
  • Sorry I didn't look at that thread. – blacktornado Dec 30 '12 at 14:46
  • You can read this google blog http://googleblog.blogspot.com.br/2007/11/road-to-better-path-finding.html and this great answer: http://stackoverflow.com/a/432854/2516160 – jean Mar 23 '15 at 19:36
  • Did he asked you about shortest path? Then your a right. Read here https://stackoverflow.com/questions/10254542/dijkstras-algorithm-does-not-generate-shortest-path?rq=1. But maybe he means the fastest path? – Micromega Dec 30 '12 at 14:33

2 Answers2

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.

Amateur Network Scientist
  • 11
  • 1
0

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

Salvador Medina
  • 5,833
  • 1
  • 19
  • 19