How Google Maps algorithm work to find the most efficient route?

How Google Maps algorithm work to find the most efficient route?

Google Maps, and most navigation applications, use an algorithm called the Dijkstra algorithm to find the most efficient route.

Google Maps looks at the streets map as a graph, made out of nodes – locations on the map, and edges – roads connecting different locations. When you try to navigate from one node to another (one location to another), the route is composed of different edges (roads) you can travel on. For example, consider the following map, with the graph representation layer over it:

Let’s say you want to go from node 25 (top left corner), to node 23 (middle-left). There are many different routes interconnecting those nodes, and every such route is defined by a series of edges we take from node to node:

  • 25–24–23
  • 25–27–23
  • 25–24–19–18–10–11–17–20–23

The question is now somewhat simpler – how do we find all those possible routes, and which route out of all those possible can we take?

Finding routes:

To find possible routes, the Dijkstra algorithm uses a pretty single process:

  1. Stat at the starting node (position) – in our case node 25.
  2. Look at all the nodes connected to this node by an edge – in our case 24 and 27.
    1. If one of them is the target node (location) – stop. We have an edge that gets us there.
    2. If non of them are the target edge, repeat the process for each one of the nodes found, using it as a starting node. We already have a path to get to them, so if there’s a path to get from them to the target, we can join the 2.

In our example, we would start with node 25. From it we will go to node 24 and 27. As neither of them are the target, we’ll keep going. From node 24, we can get to nodes 25, 19 and 23. And as 23 is our target, we can finish, and the path will be: 25–24–23.

While this process gets us a path, this is not necessarily the most efficient one. What if the road from 25–24 is clogged? We can account for that with costs.

Route costs:

We can give each edge (line connecting 2 nodes) a cost. That cost will represent the time taken to travel that edge (time taken to drive the road).

That cost will be impacted by many parameters:

  • Length of road
  • Number of lanes
  • Traffic lights
  • Traffic data (real time / estimate)
  • Many more…

In the picture above, you can see a little number above every edge – that’s it cost. We want to find the route with the lowest cost (shortest time).

We can adapt our algorithm slightly to do just that:

Put the start node into a priority queue (will return item with lowest cost), with cost 0.

Repeat:

  1. Pull the node A with lowest cost from queue
    1. If this is the target node – halt, we have a path!
    2. If this isn’t the target node, pull all of the nodes connected to it with an edge.
      1. For each of these neighboring nodes B, put them back into the queue, with the combined cost of getting to A (from the queue) plus the cost of getting from A-B.

This seemingly simple algorithm, invented by the dutch computer scientist Edsger W. Dijkstra is the backbone of any modern navigation app. The real game now is just getting as much data to have accurate costs for the edges (traffic data, accurate mapping etc…).

Sources:
The Simple, Elegant Algorithm That Makes Google Maps Possible
Iddo G. @Quora
Edsger W. Dijkstra – Wikipedia