Google Maps and graph theory

Google Maps is based on a very simple but incredibly effective algorithm: the Dijkstra algorithm. It takes its name from its inventor, Edsger Dijkstra, one of the pioneering founders of modern computing.

A walk destined to change history. It was a morning in 1956 and Dijkstra, who at the time worked as a programmer at the Centrum Wiskunde & Informatica (CWI) in Amsterdam, was walking with his girlfriend to do some shopping. When they got tired of walking they sat at a coffee shop, the Dutch scientist had an illumination: in just 20 minutes, in front of a cup of coffee, he designed the algorithm that would make him enter the history of computer science.

To understand how it works we need to introduce the concept of graph. A graph, like the one represented in the figure, is a structure formed by nodes, represented by dots, and arcs, lines that connect the nodes. Although simple, this model can be used to describe many problems. For example, nodes can represent people and arcs connect those who know each other; in anatomy, the nodes can represent the organs and the arches the blood vessels that connect them, in astronomy, the stars are nodes that, joined together by the arches, form the constellations. In our case, instead, the arches represent the roads, while the nodes are the intersections, that is all the points where it is possible to choose which road to take.

How a map becomes a graph. The streets are arches (the black lines), while the intersections are nodes (the white circles)

The arches are not all the same. When we have to choose between two possible roads we take into account the one that gets us to destination first. The factors that come into play are many: the maximum speed, the size of the road, the presence of traffic lights, traffic and so on. We can summarize them all in a single value, the (estimated) travel time of that section. This information is integrated into our graph by weights, that are the values ​​attributed to each arc. Consequently, if a “4” is written on the arc that connects the node X and the node Y, this indicates that to go from the intersection X to the intersection Y we estimate that it takes 4 minutes.

What does Dijkstra’s algorithm do? Given a weighted graph, a starting point and an endpoint within the graph itself, the algorithm finds the “minimum path” that connects the two points, that is the sequence of arcs that minimizes the sum of the weights and therefore, in the case of Maps, minimizes the estimated travel time.

A closer look. To work properly, the algorithm keeps a “cost” associated with each node, which represents the value of the minimum path to reach each node. Before starting, the nodes are assigned an infinitely high cost, which indicates that a road has not yet been found to reach it. To everyone except the starting node, which is set at zero cost (after all, arriving at the departure node from the departure node has no cost!). Moreover, it keeps a list of all the nodes that are still to be visited, which at the start includes all the nodes of the network. The algorithm always repeats the same steps. First, it extracts the node with the lowest cost from the list of nodes to visit. For each node not yet visited on the network reachable from the examined node, the algorithm evaluates how much it costs to reach this node. If the cost is lower, then it is updated, otherwise, it is left unchanged, since there is a more convenient way. The node just examined is marked as visited and starts again, until the node to be visited is not the destination.
This video shows a complete example of its operation.

Dijkstra’s algorithm always finds the fastest route. It has been shown mathematically that Dijkstra always finds the shortest path, as long as there is at least one possible route. This fact sometimes plays against us: often, in fact, in order to save a few seconds, the navigator sends us on “alternative” roads against common sense, and that we would never have dreamed of travel. On the other hand, however, it is extremely versatile, in fact, it is always able to find the fastest route. Moreover, it can take into account additional information such as traffic information or the presence of congestion, simply by going to change the weights on the graph. But how does Google know traffic information? Use the data collected by other users, but that’s another story…