How do map apps choose routes?

1. Leo and his dad want to drive to the pool. There are many ways to get there. Dad types 'pool' into the map app, and in a moment it shows a route. How did it choose?
2. First, the app sees the town in a simple way. Every junction, where roads meet, is a dot. Every road between two junctions is a line. Houses and trees do not matter for this.
3. Each line gets a number: how many minutes it takes to drive. A long highway can take less time than a short street, because cars may go much faster on it.
4. Starting from home, the app spreads out along the roads like water, adding up the minutes. At each junction it remembers the smallest total so far, and it stops when it reaches the pool.
5. The blue line is the way with the smallest total time. Look: the shortest way goes straight through the old town, but it is slow. The fastest way is longer and uses the highway.
6. Roadworks close the highway bridge. The app removes that line and adds everything up again. In a moment it shows a new best route. Traffic jams work the same way: a slow road gets a bigger number.

Tap each part to see what a map app uses to choose a route.

• Where you are. The phone listens to navigation satellites to work out where it is. The blue dot is the start of every route.
• Junctions. Each place where roads meet is stored as a dot. A route is a list of dots to pass through, one after another.
• Roads. Each road between two junctions is a line with a length. The app also knows whether it is a small street, an avenue or a highway.
• Speed. How fast cars can go on a road turns its length into a time. A fast road can be long and still be quick.
• Traffic. When many cars crowd a road, they slow down. The app colors the road red and counts extra minutes for it.
• Road closed. A closed road is taken out of the network for now. Any route that used it has to go another way.
• Best route. The blue line is the way with the smallest total time out of all the ways the app looked at.
• Arrival time. Add up the minutes along the blue line and you get the arrival time. If traffic changes on the way, the time changes too.

Tap any road to close or open it. Switch between the shortest route and the fastest route, and see when they are different.

Experiment: Is the shortest route always the fastest route?

1. Choose Fastest. Note the time and the distance of the blue route.
2. Choose Shortest. Which roads does it use now? Compare the time.
3. Go back to Fastest and tap a highway road to close it. Watch the route change.
4. Open the road again and switch on rush hour. What happens to the fastest route?

What we found: The shortest route goes straight through the old town, but its streets are slow, so it takes about twice as long as the highway route. The fastest route depends on the roads' speeds. Close a road or add a traffic jam, and the app adds everything up again and picks a new winner.

Turn on JavaScript to try it yourself.

The highway bridge is closed and there is a jam on the avenue. Tap the junctions to build the route to the pool with the smallest total time.

A map app does not see a town the way you do. It keeps a simple model: every junction is a dot and every road between two junctions is a line. This kind of model is called a network, or a graph. For each line the app stores how long the road is and how fast cars usually travel on it.

From length and speed the app works out a time for every road. Then it searches. Starting at your blue dot, it spreads out along the roads, adding up the minutes as it goes. At each junction it keeps only the smallest total it has found. When the search reaches your destination, the app follows those smallest totals back to the start. That path is your route.

The fastest route is often not the shortest. A highway that loops around a town can beat a straight line of small streets, because cars move three times as fast on it. If you ask for the shortest route instead, the app adds up kilometers instead of minutes and may pick a different path.

Roads change all day. When a road is closed, the app removes that line. When traffic is heavy, it makes that road's time bigger. Apps learn about traffic from road sensors and from phones that report, without names, how fast they are moving. Then the app searches again. Our checkout-line comparison breaks down here: in a store you can see every line, but a map app must work out the speeds from data, and its arrival time is only an estimate.

Key words

Network (graph)

A model made of dots joined by lines. In a road map, junctions are the dots and roads are the lines.

Node

One dot in a network. On a map it is a junction where roads meet.

Edge

One line in a network. On a map it is the road between two junctions.

Cost

The number given to a road that the app adds up: usually minutes, sometimes kilometers.

Shortest-path algorithm

A step-by-step method for finding the path through a network with the lowest total cost.

Estimated time of arrival

The app's best guess of when you will arrive, found by adding up the road times on the route.

Check your thinking

1. A road on your route is closed. What does the map app do?

   Show the answer

   It takes that road out and adds up the times again to find a new best way. Without that road the totals change, so the app searches again and shows the new smallest total.

2. Route A is 6 km of small streets. Route B is 9 km of highway. Which is faster?

   Show the answer

   Probably B, because cars travel much faster on a highway. Time depends on speed as well as distance. A longer road can be quicker if you drive much faster on it.

3. How does a map app store the roads of a town?

   Show the answer

   As dots for junctions and lines for the roads between them. Dots and lines are all the app needs to add up times along different ways.

4. How can a map app know that a road has a traffic jam right now?

   Show the answer

   From road sensors and from phones that report how fast they are moving, without names. Slow-moving phones on a road are a sign of a jam. The reports are combined so that no single trip stands out.

5. You ask for the shortest route instead of the fastest. What does the app add up?

   Show the answer

   The kilometers of each road. For the shortest route the cost of each road is its length. A different cost can give a different best route.