Google Maps and Graph Theory

It’s likely that you have used Google Maps before. However, it’s also likely that you don’t know how Google Maps finds these paths for you to take. Turns out they use some graph theory.

Initially, Google weighs the edges that would be part of a map, usually by either time or distance. A major part of the way they are able to find these shortest paths is by using an algorithm that actually comes up later in our book: Dijkstra’s Algorithm. That really rolls off the tongue (It’s dike-stra by the way). As given by the book, to use Dijkstra’s Algorithm:

1. Mark the ending vertex with a distance of zero. Designate this vertex as current.
2. Find all vertices leading to the current vertex. Calculate their distances to the end. Since we already know the distance the current vertex is from the end, this will just require adding the most recent edge. Don’t record this distance if it is longer than a previously recorded distance.
3. Mark the current vertex as visited. We will never look at this vertex again.
4. Mark the vertex with the smallest distance as current, and repeat from step.

Here’s an example of this algorithm being used visually:

http://www.opentextbookstore.com/mathinsociety/2.5/GraphTheory.pdf

https://motherboard.vice.com/en_us/article/4x3pp9/the-simple-elegant-algorithm-that-makes-google-maps-possible

Leave a Reply