How Google Maps Calculates The Shortest Route

Published by Elias Wirth on

In this article, we discuss optimal routing problems, Djikstra’s algorithm, and pathfinding. We ultimately present the general concepts involved in the process of finding the shortest path between two locations (in a graph).

Motivation

You probably use forms like this every day:

From: …………………………………………………………………………………………………….
To: ………………………………………………………………………………………………………….

And these forms are wonderful. Two clicks, two words, and there you go, the fastest route from point A to point B. But have you ever wondered how the route that you ultimately take is determined? What processes are involved? 

In this article, we offer answers to these questions.

Google cannot read maps

Google uses algorithms to determine our best routes. In order for these algorithms to work properly, they need the correct form of input. Let us first consider what concept makes the most sense to apply to the problem of finding the shortest path. A network of roads is best displayed in a top-down view, such as in a satellite image. In Figure 1, we see what a small Swiss town looks like from space.

Figure 1. An image of a small town in Google Maps.
Figure 1. An image of a small town in Google Maps.

Unfortunately, the pathfinding algorithm used by Google Maps does not work with satellite images. It works with a different data structure. We can always consider the network of roads as a directed graph. 


There are more graph theory articles from the Math Section:


Let us consider what Figure 1 would look like if we were to turn it into a graph, cf. Figure 2. Every intersection and every location of interest can be regarded as a vertex of the graph and the roads that connect vertices are then the edges.  

Figure 2. The image of the small town and the overlaid graph.
Figure 2. The image of the small town and the overlaid graph.

The lines in Figure 2 represent the edges of the graph and the circles are the nodes (for a basic crash course in graph theory read the Friendship Paradox). 

Denote the set of edges by \(E\) and the set of vertices by \(V.\) For each edge \(e \in E\) we denote its edge weight by \(c_e.\) 

In the case of a road network, the edge weights represent the time it takes to go from one vertex \(u\) to its neighbour \(v\) via the edge \( \{u,v\}, \) which represents a road that leads from \(u\) to \(v.\)

.The task of finding the shortest way from point A to point B can thereby be reduced to finding the shortest path on a weighted graph. There are a lot of different algorithms that can do this but we only want to discuss the one introduced by Dijkstra. (Google Maps most likely uses \(A^*\) search.)

Dijkstra’s algorithm was published in 1959 by Edsger W. Dijkstra. The algorithm was and still is important in the area of pathfinding. It is explained in the following video by the YouTube-channel Nathaniel Fan:

Problems

In practice, there are of course a lot more complications involved in the process of finding the shortest path, such as:

  • It is not trivial to create a graph from the knowledge of where roads and locations are. 
  • Traffic jams affect travel time and it is not possible to predict them all in advance. 
  • Some roads may be closed during certain hours during the day making the graph time-dependent.

But, as we all know, the process of pathfinding is getting better every year and we can hopefully look forward to new discoveries in this area of research. 

Conclusion

We explained the core idea behind Google Maps’ algorithm, introduced Dijkstra’s algorithm, and discussed further difficulties involving pathfinding. For more articles on graph theory, especially ones that are more in-depth, the following are recommended:


Elias Wirth

The Math Section is my personal website dedicated to applications of mathematics in everyday life. The intention behind this project is to make mathematics more approachable to the public while staying mathematically rigorous. I have a Bachelor's degree in Mathematics from the University of Berne and am currently working on my Master's degree in Mathematics at the ETH Zurich.

3 Comments

Chris · December 31, 2018 at 15:15

With a title of “How Google Maps Calculates The Shortest Route”, I expected to learn how Google Maps calculate the shortest route.

While Dijkstra’s Algorithm is at the core, there’s no way that works. I expected at least some treatment of A* and a discussion of heuristic. Though I’m sure they use something more like D* to account for changing traffic and road closures.

    Elias Wirth · January 1, 2019 at 14:40

    Hey Chris,
    Thank you very much for your comment.
    With this article, in particular, the plan was to discuss the basic principles involved in the process of pathfinding and while yes, Dijkstra’s is most certainly not used by Google, it is still the most easily understandable of these algorithms. I value the basic understanding of the concepts involved in the algorithms higher than discussing the maybe more relevant A* star search. This is just a decision I made for this post, which not everyone is going to be satisfied by. I do, however, try to write on a broad spectrum of mathematical depth (some articles go into more detail than others) and this article was definitely on the lighter side. Hopefully, you still enjoyed reading it and if you would like to write a short piece on the different search algorithms I would be open to a collaboration. I wish you a happy new year, Chris.
    Best regards,
    Elias

Patrick · December 31, 2018 at 22:06

interesting that it selects ABDF as the preferred route over AEDF, even though both are the same distance, merely because the first leg in ABDF is shorter than the first left in AEDF. The ACD route must wind around a lot (or have a lot of switchbacks) for it to be a distance of 14 when ABD and AED are each only 9; it would be somewhat unusual to have one route between two other routes that are both shorter.

Leave a Reply