How Google Maps Calculates The Shortest Route

By Elias Wirth

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.

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: