Skip to main content



How does Google Maps work?

Google Maps helps millions of people get from point A to point B seamlessly everyday. So how does it work?
As the article explains, it is actually a graph theory problem. Think of your current position as a node and your destination as another node, and then there are many other nodes in between your current position and your destination. The weight of each edge that connects any two nodes represents the distance between those two nodes. The amount of traffic could also affect the weight of each edge.
The algorithm that is used to find the shortest path between your current position node and your destination position node is called Dijkstra’s algorithm, and the article has a fairly simple explanation and graphics that illustrate the algorithm. Starting from the first node, we iterate through each neighbor and assign the neighbor a value, which represents the distance from your starting node to the new node. This distance is quantified by the weight of the edge that connects those 2 nodes. We then repeat this process for all the neighbors and record on each new node the value of the shortest distance from that node to the starting node.
Now there is an interesting side effect if Google implemented the above Dijkstra’s algorithm to Google Maps. While you are trying to find the shortest path from Austin, Texas to New York City, you would also find the shortest path from Austin, Texas to Orlando, Florida because the algorithm simply iterates on every neighboring node, so the search for the shortest path would expand in all directions from Austin, Texas. This is considered wasted compute. Google can use a modified application of Dijkstra’s algorithm to be more efficient. Since we know the general direction from Texas to New York, we can purely choose neighboring nodes that are in that direction, which will decrease compute and time. 
http://motherboard.vice.com/read/the-simple-elegant-algorithm-that-makes-google-maps-possible

Comments

Leave a Reply

Blogging Calendar

September 2015
M T W T F S S
« Aug   Oct »
 123456
78910111213
14151617181920
21222324252627
282930  

Archives