The fastest route: the mathematics of Google Maps

6 May 2025
5 minutos
Blog

Google Maps, Apple Maps or Waze have become an essential part of the daily lives of billions of people around the world, who need to consult in real time the ideal route to their next meeting, the rural house where they will spend their holidays or the restaurant where they are going to have dinner.

For many people, the fact that these applications are not only able to show them the ideal route, but also take into account factors such as traffic or possible incidents along the way, is practically magic. However, the answer lies in mathematics. In this sense, applications such as Google Maps model streets as a graph (a network of nodes and edges) and use intelligent algorithms such as Dijkstra and A* to calculate the best route.

The representation of the city

A graph is basically a set of points connected by lines. Applied to the street structure of a city, each point (or node) represents an intersection or a place of interest and each line(edge) represents a road or street connecting two nodes. In addition, a weight can be attached to these edges (e.g., the distance in kilometres or the average time it takes to travel that street).

Modelling the city as a graph allows us to apply mathematical tools to search for optimal paths. How? First, every time we ask Google Maps for the best route to a given address, the application "translates" the origin and destination location into nodes within a huge graph, which represents all the streets, roads, etc. in a given region. Finding the fastest route between those two points is, in reality, equivalent to solving the "shortest path" in that graph. To achieve this, most of these applications rely on special algorithms that explore the network of nodes and artists in search of the optimal path: Dijkstra's algorithm and the A* algorithm are the most popular.

Dijkstra and A*: exploring the shortest path

Dijkstra's algorithm, named after the scientist Edsger Dijkstra, is a classic method for finding shortest paths in a graph. In essence, Dijkstra takes an initial node (e.g. our home address) and systematically explores all possible routes to the destination node (e.g. our office) by calculating the cumulative distance of the various possibilities.

Thus, from the initial node, it "visits" first the nearest accessible place, then the one closest to it, and so on,always choosing the path with the shortest cumulative distance. In this way, each time the algorithm reaches a new junction, it updates the shortest known distance to that point. If it finds a shorter route to a place it has already reached by another route, it readjusts that calculation.

In the end, the algorithm returns the path with the shortest total distance (or shortest time, if we use time as a weight) from the origin to the destination. This way of calculating distances and times is the basis of most traditional GPS systems and is used as part of any navigation and route planning system.

The A* algorithm, on the other hand, takes the robustness of Dijkstra and adds a touch of extra intelligence, introducing "intuition" as a fundamental part of the search. A* combines two factors when it explores the graph: on the one hand, the distance travelled from the start (as Dijkstra did) and, on the other hand, an estimate of the distance to the destination. Each time A* evaluates where to move to, it adds up what it has already moved + what it (estimates) it still has to move.

This estimate, called a heuristic, is usually based on the straight-line distance to the destination or some other estimate. For example, if we are looking for a route in a northerly direction, A* "senses" that, all things being equal, going north is likely to get him closer than going south. Thanks to this strategy, A* prioritises exploring first the paths that seem most promising for reaching the destination, which, in practice, allows it to visit fewer nodes than Dijkstra and therefore find the solution faster in most cases.

Real-time traffic and other adjustments

But calculating the shortest path in a road network is only part of what these applications do. The reality of driving in the city includes taking into account traffic, accidents, road works, etc. In recent years, applications such as Google Maps integrate this data in real time, to adjust the recommended route on the fly. To do this, edge weights (representing travel times) can be dynamically recalibrated according to current conditions. If a normally fast highway becomes congested, the algorithm detects this and "penalises" it by increasing its weight, so that an alternative route may become more attractive.

Where do companies like Google get this instant traffic data? The answer lies in our own smartphones. When we use Google Maps, the phone sends anonymous location and speed data to the company's servers. By aggregating the information from millions of users, the system detects patterns: for example, if many mobiles are moving very slowly on the same road, that suggests a traffic jam. In addition, it also relies on partnerships with local authorities (e.g. municipal traffic sensors) and predictive modelling: it has accumulated historical data that allows it to predict regular traffic jams by time and day, using artificial intelligence algorithms to anticipate congestion. In this way, the algorithm not only calculates routes on a static map, but on a live map, reflecting what is happening minute by minute on the streets.

And although, as we have seen, graph routing algorithms play a fundamental role in directing us to our destination, they are not exclusive to GPS navigation; they have countless applications in technology and other fields, such as video games, logistics or applied AI, improving the movements of NPCs (non playable characters), optimising delivery or public transport routes, or helping autonomous vehicles and robots to avoid obstacles.