How Does a Map App Find the Quickest Route?

Nearest first fixes junctions in the order of their time from the Start. So by the time it fixes the Goal, it has fixed every junction that is quicker to reach than the Goal, in every direction, even behind the Start. The patch is centered on the Start, with the Goal on its edge: a diamond in this town, where streets run only east–west and north–south, and a rough circle on a map with roads every way.

Either way, its area grows as the square of its reach. A circle of radius r has area πr², and a diamond reaching r blocks each way has area 2r². Ten times the trip, a hundred times the work: fine for a town, hopeless for a continent. In 2015, eight route-planning researchers measured it on a standard test map, the roads of Western Europe, with 18 million junctions. For a trip between two junctions picked at random, nearest first looked at about 9.3 million junctions, half the continent, and took 2.2 seconds on a fast computer. A map app that answers millions of people can’t spend 2 seconds on each.

Search from both ends

The first trick: start a second search at the Goal, working backwards along the roads, and take turns. Each only has to reach about halfway.

But both searches still spread out in every direction, even away from each other. Looking for Pokhara from Bhaktapur, you wouldn’t check the roads to Biratnagar first: you know which way Pokhara is.

Can a search use the direction without losing the guarantee of the quickest route? Yes, with one more number for each junction: a lower bound on the time still left to the Goal, a number the real time can never be less than. Call it h(v) for junction v. Then, instead of fixing the junction with the smallest time so far, fix the one with the smallest

$$\text{time so far} + h(v),$$

the junction that seems to be on the quickest whole journey. This search is A* (said “A star”), and a lower bound used this way is called a heuristic.

The easiest lower bound is the straight line: no road is shorter than the straight line between its ends, so when kilometers are added up, the straight-line distance to the Goal, worked out from the junctions’ positions by the distance formula, is a lower bound.

Why aiming is still exactly right

Aiming changes the order in which junctions are fixed. Why is the answer still the quickest route? Because A* is nearest first in disguise.

Give every road from u to v a new weight:

$$\text{new weight} = \text{old weight} - h(u) + h(v).$$

Look at what this does to a whole route. Here is a route from S through a and b to the Goal G, with the old weights 4, 3 and 5 minutes and the lower bounds h(S) = 9, h(a) = 6, h(b) = 4, h(G) = 0.

Road	Old weight	− h(start of road)	+ h(end of road)	New weight
S to a	4	− 9	+ 6	1
a to b	3	− 6	+ 4	1
b to G	5	− 4	+ 0	1
Total	12			3

Each h is added on one road and taken away on the next, so they cancel in pairs, like a sum that telescopes. Only the first and last survive:

$$\text{new total} = \text{old total} - h(\text{S}) + h(\text{G}) = 12 - 9 + 0 = 3.$$

The same happens on every route from S to G: each total goes down by the same amount, h(S) − h(G). (Another route, S to c to G, with old weights 6 and 7 and h(c) = 5, goes from 13 to 2 + 2 = 4, which is 13 − 9.) So the quickest route with the old weights is the quickest with the new.

Now the disguise. With the new weights, a junction’s time from S is its old time so far − h(S) + h(v). Taking the same h(S) from every junction changes nothing about which is smallest, so nearest first on the new weights fixes junctions in the order of time so far + h(v): it is A*.

And nearest first is right as long as no weight is negative, as the 6–8 topic showed with its treasure path. So A* is exactly right whenever every new weight is zero or more:

$$h(u) \le \text{old weight of the road from } u \text{ to } v + h(v) \quad \text{for every road}.$$

A lower bound with this property is called consistent. In words: driving one road can’t bring the bound down by more than the road takes. The straight line passes, because of the triangle inequality: one side of a triangle is never longer than the other two together. The straight line from u to the Goal is at most the straight line from u to v plus the straight line from v to the Goal, and the road from u to v is at least as long as the straight line between them.

The ellipse

How much does aiming save? Picture open country where you can walk anywhere, with a lake between the Start and the Goal, so that the quickest way goes round it and is longer than the straight line D between them: k times as long, so of length kD, with k = 1.25.

A* only fixes a junction P whose time so far plus h(P) is at most the route’s length: until the Goal is fixed, some junction on the quickest route is waiting with a total of at most kD, so a larger total never comes first. The time so far is at least the straight line from the Start to P, and h(P) is the straight line from P to the Goal. So every junction A* fixes has

$$SP + PG \le kD.$$

The points whose distances to two fixed points add up to at most a fixed amount fill an ellipse, with the two fixed points as its foci. Gardeners draw one with a loop of string round two pegs, the pencil keeping the string tight. Grade 10 Optional Mathematics meets the ellipse as a slice through a cone; here it turns up as the shape of a search.

The ellipse’s long axis is the route’s length, kD, so its half-axes are a = kD/2 and b = (D/2)√(k² − 1), from Pythagoras’ theorem: the end of the short axis is equally far from both foci, so each distance is half of kD, and it makes a right triangle with the half-axis b and half the distance D between the foci. Its area is πab, against π(kD)² for nearest first’s circle, so

$$\frac{\text{ellipse}}{\text{circle}} = \frac{\sqrt{k^2 - 1}}{4k}.$$

For k = 1.25 that is 0.75 ÷ 5 = 15%. The straighter the quickest route (k close to 1), the thinner the ellipse; when the route is the straight line itself, k = 1 and the ellipse squeezes down to the line.

A map app doesn’t add up kilometers. It adds up minutes, because a long highway can be quicker than a short road through a crowded bazaar. Then the straight line must be turned into a time, and it has to stay a lower bound: the straight-line distance divided by the fastest speed anywhere on the map. Nothing can go faster, so nothing can arrive sooner.

But most roads are much slower. On the Western Europe test map the fastest roads were given 130 km/h and the slowest 10 km/h, so for a trip through town streets, “straight line at 130 km/h” says a few minutes when the truth is half an hour. A bound that low hardly aims; the researchers found the gain on road maps timed this way “small or non-existent”.

The fix is to measure instead of guessing from geometry. Before anyone asks, pick a few landmarks, junctions near the edges of the map, and work out once, by nearest first, the quickest time from each landmark to every junction. Store the tables. Now the triangle inequality gives a much better lower bound.

Going from the landmark L to the Goal G by way of v can’t be quicker than the quickest way from L to G:

$$d(L, G) \le d(L, v) + d(v, G), \quad \text{so} \quad d(v, G) \ge d(L, G) - d(L, v).$$

Both numbers on the right are in L’s table, and if the landmark lies behind v, seen from the Goal, the bound is close to the truth. On two-way roads the times the other way round give a bound too, d(L, v) − d(L, G); with several landmarks, take the largest bound. It is consistent, so A* stays exactly right, and it is measured in whatever the map adds up, so it aims as well with minutes as with kilometers.

This method is called ALT, for A*, landmarks and triangle inequality. Andrew Goldberg and Chris Harrelson published it in 2005. In the widget, choose Landmarks: the four purple diamonds are its landmarks, near the corners. Over the same 150 random pairs it looked at about 15% of nearest first’s junctions, with minutes and with kilometers alike.

The price is paid in advance, in tables. That idea, work done once before anyone asks, so that every question is quick, leads to the fastest method.

Driving from Bhaktapur to Pokhara, you leave the side streets as soon as you can, stay on the highway, and leave it only near the end. Most junctions are side streets that no long trip passes through. The best method builds this into the map with shortcuts.

Remove the junctions one at a time, the least important first. When you remove a junction v, look at each pair of its neighbors. If the only quickest way between them went through v, add a shortcut road joining them directly, with the time of that way. Otherwise another way is as quick, and nothing is needed. Either way, every quickest time between the junctions left is kept.

The order you removed the junctions in gives them a rank, 1 for the first removed up to 9 for the last. This is a contraction hierarchy (to contract a junction is to remove it this way). Robert Geisberger, Peter Sanders, Dominik Schultes and Daniel Delling published the method in 2008.

Asking a question

A question is then answered by two searches, one from each end, each moving only upward, along roads and shortcuts to junctions of higher rank. The smallest total through a junction both reached is the quickest time. In the widget, the blue and green roads were the two searches.

Why can they never miss? Take any quickest route. Wherever it dips to a junction ranked lower than both junctions next to it on the route, that junction was removed while both of them were still there. So either a shortcut joined them, or another way at least as quick went round through junctions removed later. Swap that in and the dip is gone, and the route is no slower. Each swap takes out one junction and puts in only junctions ranked higher, so the swapping can’t go on forever. When no dips are left, the route climbs from the Start to its highest junction and comes down to the Goal. The upward search from the Start finds the climb, the upward search from the Goal finds the descent backwards, and they meet at the top.

• What Is the Quickest Way Across the Map? (Grades 6–8) Nearest first itself, why it is right, and where a negative weight breaks it.
• How Do You Connect Every Village with the Least Cable? Joining every place at the least cost, by a greedy rule Dijkstra also gave in his 1959 paper, after Jarník and Prim.
• Why Do Flights to America Fly Near the North Pole? The shortest way on a globe, where the “straight line” is a great circle.
• Aiming at the goal: A* (Grade 12 Computing) Write nearest first and A* as programs, on a map of Nepal’s highways. Grade 10 Computing starts the story in How a map app finds a route.
• How Does a Computer Play Chess? (Computing, Going Further 9–12) Another search that saves work by knowing which possibilities can’t matter.