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.
6 Answers
Google maps is using Dijkstra's Shortest Path Algorithm. It calculates the connections between pairs of elements or so called nodes. The connection between nodes are called edges. Each edge has a weight. The weight of an edge can represent distance, time, or anything that models the "connection" between the pair of nodes it connects. These weights are essential for Dijkstra's Algorithm. In that way you can find the shortest path between nodes. Particularly, you can find the shortest path from a node (called the "source node") to all other nodes, producing a shortest-path tree.
Google map is using some very sophisticated algorithm. It might be any heuristics such as A*; but, it is definitely not Dijkstra's algorithm. My finding;
1] Many times it shows path of less traffic, which changes with time but Dijkstra algorithm would give a single path in all situations.
2] Me, and my friends were visiting some place; we all have started google map at the same time. If google map was giving optimal shortest path then our maps must had provided us the same path; but it did not happen. It means they are not using any exact algorithm.
Udacity data structure and Algorithm nanodegree claims that Google is using an algorithm similar to A* algorithm; however, it requires citation. You may also visit quora discussion
Related