Which algorithm does Google maps use to compute the direction between 2 points?

Question

I wonder which algorithm Google maps use to compute the direction between 2 points ? Has Google ever mentioned about it ?

p/s : I am asking the algorithm which google use to find the shortest route between 2 points.

Answer 1

To the best of my knowledge Google has never publicly stated which algorithm it uses of P2P queries. Although the current state of the art from the literature in terms of query times is the Hub labelling algorithm proposed by Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . A through and excellently written survey of the field was recently published as a Microsoft technical report http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

The short version is...

The Hub labelling algorithm provides the fastest queries for static road networks but requires a large amount of ram to run (18 GiB).

Transit node routing is slightly slower, although, it only requires around 2 GiB of memory and has a quicker preprocessing time.

Contraction Hierarchies provide a nice trade off between quick preprocessing times, low space requirements (0.4 GiB) and fast query times.

No one algorithm is completely dominate...

This Google tech talk by Peter Sanders may be of interest

https://www.youtube.com/watch?v=-0ErpE8tQbw

Also this talk by Andrew Goldberg

https://www.youtube.com/watch?v=WPrkc78XLhw

An open source implementation of contraction hierarchies is available from Peter Sanders research group website at KIT. http://algo2.iti.kit.edu/english/routeplanning.php