ALGO·III Algorithms Chapter 24 of 65
The navigator
We build a navigation app and put it through its paces on the Moscow metro. The wave Dijkstra invented in twenty minutes on the terrace of an Amsterdam café; a glance toward the goal, borrowed from the robot Shakey; money that goes around in a circle and grows; the preprocessing no map service can do without. At the end, the answer to the course’s third big question.
Algorithms
- 20 Search and sort
- 21 Divide and conquer
- 22 Dynamic programming
- 23 Greedy
- 24 Shortest paths you are here
- 25 Flows, matchings
- 26 Randomness
- 27 Text search
Builds on: 19 · Six handshakes 18 · Who is next 23 · Greed and electricity
What you will take away
- plot the shortest route through a weighted graph with Dijkstra’s algorithm and a heap, and understand why it is right
- speed up the search with the A* heuristic and with landmarks, and know when a heuristic doesn’t spoil the answer
- find negative cycles with the Bellman–Ford algorithm and see arbitrage in them
3How does a navigation app find the shortest route among millions of roads in a second?
The last chapter ended with the wires laid and no way yet to drive anywhere. Even earlier, in Chapter 19, the same wall rose in the metro: the wave from Sokolniki to Moskva-Siti chose the Big Circle line, ten edges instead of thirteen, but by our estimate it took 33 minutes against 26 through the center. Breadth-first search counts edges; a passenger counts minutes. We will build a navigation app that counts minutes and send it on a series of trips. Each trip breaks the current version and forces us to invent the next, and the last one answers the course’s third big question: how does a navigation app find the shortest route among millions of roads in a second?
Trip one: Sokolniki to Moskva-Siti
The metro graph is the one from Chapter 19: stations are vertices, rides between stations and transfers are edges. But now every edge carries a number, the minutes it costs. Such a graph is called weighted, and the length of a path in it is the sum of the weights of its edges. Our minutes are estimates: a ride is the straight-line distance covered at an average 41 km/h, plus half a minute at the platform, and a transfer is four minutes. The metro’s timetable is more complicated, but this is enough for our navigation app: what matters is that the weights differ. The function load_metro(minutes=True) from the module cs.graphs returns a dictionary of dictionaries: graph[station][neighbor] is the minutes.
How do we teach the wave to count minutes? There is a brute-force way, if a wasteful one. Cut every ride into pieces a tenth of a minute long by putting dummy stations between them. Then all the edges are equal, and breadth-first search finds the fastest route: the wave crawls along tenths of a minute. But the dummy stations alone number more than ten thousand, and the wave spends almost all its time crawling through them from one metro station to the next.
What if, instead of crawling, the wave jumped? When it reaches a station at time $t$, we can write in a calendar right away: “the wave will reach the neighboring station at time $t + w$,” where $w$ is the weight of the ride. This is the event calendar from Chapter 18: take the nearest event out of the heap, process it, and perhaps put new ones in. The wave may “arrive” at a station several times by different roads, and the calendar will hold several entries for it. Only the first, earliest one matters; the rest we throw away when they come up, like the stale wires in Prim’s algorithm from the last chapter.
Amsterdam, 1956. Twenty minutes on a terrace
Here is Dijkstra’s recipe in words. Every vertex has an estimate of its distance from the start: 0 for the start itself and infinity for the rest. Repeat while there is work to do: take the unsettled vertex with the smallest estimate and declare it settled. Then for each of its neighbors check whether the road through the newly settled vertex is shorter; if it is, lower the neighbor’s estimate. This check is called relaxation of the edge: the neighbor’s estimate relaxes, moving closer to the truth. Vertices are settled in order of their distance from the start, and the wave spreads by the minute, like a fire through grass. Press “Steps” or drag the slider under the picture: green vertices are settled, yellow ones already have an estimate, and the highlighted edges lead to each vertex along the best road known so far.
At first B is reached directly, in 4 minutes, but as soon as C is settled, B’s estimate drops to 3: going through C is faster. For a while the heap holds both entries, (4, B) and (3, B), and the stale one is thrown away by the continue line. The wave reaches F in 12 minutes along five edges, A–C–B–D–E–F, although a road of only three edges exists, A–B–D–F, which costs 15 minutes.
On the Moscow metro we can stop as soon as the goal is settled: the rest of the wave is of no use to us. To recover the route, we walk back from the goal along prev.
Twenty-six and a half minutes through the center, with one transfer, from the Lenin Library station to Aleksandrovsky Sad. In Chapter 19 we laid out this route by hand; now an algorithm has found it. Before reaching the goal, Dijkstra settled 141 of the 312 stations, and that number is what we will fight in the next trip.
Why the wave makes no mistakes
Dijkstra declares a vertex settled and never touches it again. How can we be sure a shorter road won’t turn up later? Write $\delta(v)$ for the true shortest distance from the start to $v$, and $\mathrm{dist}[v]$ for the algorithm’s estimate. The estimate is never smaller than the truth: every estimate is the length of some path that was found.
If all edge weights are non-negative, then at the moment a vertex is declared settled, its estimate equals its shortest distance from the start.
Suppose not, and let $u$ be the first vertex to be settled with a wrong estimate: $\mathrm{dist}[u] > \delta(u)$. Take a shortest path from the start to $u$. The start is settled and, at this moment, $u$ is not; so the path has a first unsettled vertex $y$, and right before it a settled vertex $x$. When $x$ was settled its estimate was correct, since $u$ is the first mistake, and the edge $x \to y$ was relaxed: $\mathrm{dist}[y] \le \delta(x) + w(x, y) = \delta(y)$, because the beginning of a shortest path is itself a shortest path. Further along the path, from $y$ to $u$, the weights are non-negative, so $\delta(y) \le \delta(u)$. Putting it together: $\mathrm{dist}[y] \le \delta(y) \le \delta(u) < \mathrm{dist}[u]$. But the algorithm chose $u$ as the unsettled vertex with the smallest estimate, and the unsettled $y$ has a smaller one. A contradiction.
The reasoning is of the same kind as in Chapter 23: the greedy choice, the nearest of the unsettled vertices, is safe. Non-negative weights were used in one place only: $\delta(y) \le \delta(u)$, “further along the path the road doesn’t get shorter.” Remember that spot: on the third trip the weights will turn negative.
What the wave costs
Every vertex is settled once, every edge is relaxed at most once from each end, and every successful relaxation puts one entry into the heap. So there are at most $2m$ entries, and each heap operation costs $O(\log n)$. In all, $O((n + m) \log n)$. The 1959 paper had no heap to work with (Williams would describe one only in 1964), and Dijkstra found the nearest vertex by scanning all the unsettled ones: $n$ times $n$ comparisons, $O(n^2)$. For 64 Dutch cities that is instant. A bigger city makes a harder test: a square one laid out in blocks, where intersections are vertices and the streets between neighboring intersections are edges with a random time from 1 to 9 minutes.
Four times as many intersections, and the scan takes sixteen times longer, while the heap takes about five times longer: the extra beyond four comes from the logarithm in the estimate and from a bigger table fitting less well into the cache. On 160,000 intersections the heap needs a fraction of a second, and the scan would need something like ten minutes. Here, unlike the if u in done check in the first cell, a stale entry is recognized by d > dist[u]: the heap holds an estimate worse than one already known. Both ways work equally well.
Can it be done faster than $O((n + m) \log n)$?
In 1984 Michael Fredman and Robert Tarjan invented the Fibonacci heap, in which decreasing an element’s key costs $O(1)$, amortized, and with it Dijkstra’s algorithm runs in $O(m + n \log n)$. The factor $\log n$ on the vertices can’t be removed as long as the algorithm hands out vertices in order of distance: otherwise it would sort faster than the lower bound from Chapter 20 allows. In practice Fibonacci heaps are complicated and run slowly on modern hardware, and a binary heap with stale entries, like ours, is usually enough.
Trip two: toward the goal
To find the way from Sokolniki to Moskva-Siti, Dijkstra settled 141 stations, almost half the metro, including Preobrazhenskaya Ploshchad and Bulvar Rokossovskogo, which lie in the opposite direction. The wave spreads equally in all directions: it has no idea where the goal is. A person with a map doesn’t search like that; they look straight toward where they are going. How can we teach this to the algorithm without losing the guarantee of a shortest path?
The idea of A* fits in one line. Dijkstra takes from the heap the vertex with the smallest distance traveled, $g(v)$. A* takes the vertex with the smallest sum $g(v) + h(v)$, where $h(v)$ estimates how much is still left from $v$ to the goal. Such an estimate is called a heuristic. On a map, the natural heuristic is the straight-line distance to the goal divided by a speed. Stations behind you get a large sum and wait, and the wave stretches out toward the goal.
But the estimate is allowed to err in one direction only. If $h$ overestimates what is left, the algorithm can pass by the shortest path, judging it worse than it is. A heuristic that never overestimates the distance to the goal is called admissible. For the metro, this means the straight-line distance must be divided by a speed that no train in our model ever exceeds. Then the goal certainly can’t be reached in less than $h$.
It is easier to prove that an admissible heuristic is enough under a slightly stronger condition, one that holds almost always: consistency.
Suppose the heuristic is consistent: $h(u) \le w(u, v) + h(v)$ for every edge, and $h = 0$ at the goal. Then A* finds a shortest path to the goal.
Change the edge weights: $w'(u, v) = w(u, v) - h(u) + h(v)$. By consistency, all the new weights are non-negative. The length of any path from the start $s$ to the goal $t$ in the new weights is the same sum, except that the intermediate $h$ terms cancel: $L' = L - h(s) + h(t)$. All paths from $s$ to $t$ have shifted by the same amount, so a shortest path stays shortest. And Dijkstra in the new weights takes the vertex with the smallest $g'(v) = g(v) - h(s) + h(v)$, which is the one with the smallest $g(v) + h(v)$, the same choice A* makes. So A* is Dijkstra’s algorithm on a graph with non-negative weights, and by what we proved above, it is right.
The straight-line distance is consistent: by the triangle inequality, the straight line from $u$ to the goal is no longer than the straight line from $u$ to $v$ plus the straight line from $v$ to the goal, and no train can cover the edge $u \to v$ faster than a straight line at the top speed. Every consistent heuristic is admissible (add up the inequalities along a shortest path to the goal); the converse doesn’t always hold, but A* with an admissible heuristic also finds a shortest path, only it sometimes settles the same vertex more than once.
That leaves the top speed. We compute it from the data: for every edge, how many kilometers of straight line it covers per minute. The answer is about 39 km/h, a little under the 41 km/h of our model, because every ride includes half a minute at the platform. The fastest rides are the longest ones, where the stop matters least.
The answers agree to the tenth of a minute, and the work shrinks severalfold: 56 stations instead of 141, 78 instead of 255, 5 instead of 33. Go back to the metro widget and switch on “A*”: the faint patch of settled stations stretches out along the route. And in the grid widget, push the slider past one. The heuristic starts to overestimate, and the search races to the goal even faster, but the path sometimes comes out longer than the shortest. That is the choice people make when speed matters more than accuracy, for instance in video games, where hundreds of characters have to find their way every second.
Trip three: money instead of minutes
The navigation app has learned minutes. Now let the edges carry money: a courier pays for toll roads, and on some stretches he is paid extra instead, say, for a package he picks up on the way. A bonus is a negative weight. From A to D the courier can go through C, paying 2 and then 2 more, or through B: pay 5, but earn 4 on the stretch from B to D. What will Dijkstra say?
Dijkstra settled D at a price of 4: at that moment it was the nearest unsettled vertex. Then B was settled, and it turned out that through B the way to D costs only 1, but Dijkstra never touches a settled vertex again. What broke is the spot in the proof we asked you to remember: “further along the path the road doesn’t get shorter.” With a negative edge, it does.
The second function makes no choices at all. It runs relaxation over every edge in turn, round after round, $n - 1$ times. This algorithm bears the names of Richard Bellman, the man who named dynamic programming (Chapter 22), and Lester Ford Jr.; they published it in 1958 and 1956, and at about the same time Alfonso Shimbel and Edward Moore found it as well. And it is dynamic programming too: after $k$ rounds, every estimate is no worse than the best path with at most $k$ edges.
If the graph has no cycles of negative length reachable from the start, then after $n - 1$ rounds of relaxing all the edges, all the estimates equal the shortest distances.
We prove by induction on $k$ that after $k$ rounds, $\mathrm{dist}[v]$ is no greater than the length of any path from the start to $v$ with at most $k$ edges. For $k = 0$, only the start itself has a path without edges, and its estimate is 0. Suppose this holds for $k$, and take a path to $v$ with $k + 1$ edges whose last edge is $u \to v$. After $k$ rounds, $\mathrm{dist}[u]$ is no greater than the length of the path’s beginning up to $u$, and in round $k + 1$ the edge $u \to v$ was relaxed, so $\mathrm{dist}[v] \le \mathrm{dist}[u] + w(u, v)$, which is no more than the length of the whole path. If there are no negative cycles, any cycle can be cut out of a shortest path without making it longer, so there is a shortest path with no repeated vertices, and it has at most $n - 1$ edges. So after $n - 1$ rounds the estimates are no greater than the shortest distances, and they are never smaller: every estimate is the length of some path.
The price is speed: $n - 1$ rounds of $m$ edges each is $O(nm)$ instead of $O(m \log n)$. For the metro that is a quarter of a million relaxations, done in an instant; for the roads of a whole country it is hopeless. So Bellman–Ford is used only when negative weights can’t be avoided, for example when the edges carry exchange rates.
Money going around in circles
If there is a cycle of negative length, there is no shortest path at all: one more pass around such a cycle makes the path shorter still, and so on forever. Such a cycle is called a negative cycle. But such a cycle is easy to spot: if some estimate still decreases in round $n$, there is a cycle, since without one everything would have settled within $n - 1$ rounds.
A negative cycle can come in handy on the currency market. Suppose a euro buys 0.96637 Swiss francs, a franc buys 167.54 yen, and a yen buys 0.0061825 euros. Change a thousand euros around the circle: if more than a thousand come back, we have found an arbitrage, a risk-free profit from a single inconsistency between the rates. A round of exchanges pays off when the product of the rates is greater than one. The logarithm turns the product into a sum: $r_1 r_2 r_3 > 1$ if and only if $\log r_1 + \log r_2 + \log r_3 > 0$, that is, when $(-\log r_1) + (-\log r_2) + (-\log r_3) < 0$. Write $-\log(\text{rate})$ on every edge, and a profitable round of exchanges becomes a negative cycle.
A thousand euros turned into 1,000.98 in three exchanges. We start “from everywhere at once,” with zeros at every vertex, which is the same as adding a dummy start vertex with edges of weight 0 to every currency: then any cycle is reachable. And to land on the cycle, we have to step back along prev $n$ times. The vertex that changed in the last round may itself hang on a tail leading out of the cycle, but a chain of prev links longer than $n$ must repeat a vertex, which means it has entered the cycle. Keep something else in mind too: Bellman–Ford finds some negative cycle, not necessarily the most profitable one. Finding the most profitable round with no repeats is one of the problems that Chapter 57 will call NP-hard.
The table is made up: the rates look like market rates, but a skew is hidden in them on purpose, so that euros buy slightly more francs than the other rates imply. On an exchange such skews last a fraction of a second: programs hunt for them, and the first few trades even the rates out. And the exchange fee eats the profit even sooner; move the slider in the widget. Today’s rates and their history are in the currency converter on this site; see whether you can find a cycle in them.
All pairs at once
Sometimes you need the distances between all the stations at once: to find the two farthest apart, or to learn how long an average passenger rides. You could run Dijkstra from every station. Or you could do it more briefly, with the three nested loops of Robert Floyd and Stephen Warshall (1962). This is dynamic programming from Chapter 22 again. Let $d_k[i][j]$ be the shortest path from $i$ to $j$ that changes trains only at stations among the first $k$. When we add station $k$, we either do without it or go through it: $d[i][j] = \min(d[i][j],\; d[i][k] + d[k][j])$. After all the $k$, the table is complete. Negative edges are allowed, negative cycles are not: they would show up as a negative number on the diagonal.
Thirty million checks take two or three seconds. The two stations farthest apart in our model are 97 minutes from each other, and between two random stations the average is 36 minutes. Floyd–Warshall takes $O(n^3)$ time, and that is a lot: Dijkstra from every vertex gives the same in $O(n (n + m) \log n)$, which is faster on sparse graphs like the metro. But the three lines of the loop are hard to get wrong, and they work unchanged with negative edges.
Trip four: millions of roads
Our metro graph has 312 stations. The road network of Western Europe, on which researchers test their routing algorithms, has about 18 million intersections and 42 million road segments. Our heap got through 160,000 intersections in about a third of a second; on Europe, by a rough estimate, the same code would spend half a minute on every route. A* with a straight line helps, but on roads it helps less than you might expect: a straight line doesn’t know that between you and your goal lies a river with a single bridge. So how does a phone answer before you lift your finger from the screen?
What saves the day is preprocessing: we spend a lot of time once, in advance, so that every query afterward is fast. We have already done one piece of preprocessing: after two or three seconds of Floyd–Warshall, any route through the metro is a single table lookup. But for 18 million intersections a table of all pairs holds $3 \cdot 10^{14}$ numbers, more than a petabyte. We need a more modest kind of preprocessing, and several kinds have been invented.
Landmarks. Choose a few vertices at the edges of the map and compute in advance the distances from each of them to all the others. The triangle inequality gives an estimate: if it is 50 minutes from landmark $L$ to the goal and 20 to vertex $v$, then from $v$ to the goal is at least 30, or else you could get from $L$ to the goal in under 50. In general, $d(v, t) \ge |d(L, t) - d(L, v)|$, and the maximum over the landmarks is an admissible heuristic for A*. It measures by roads, not by straight lines, so it knows about the rivers and the bridges. This method (Andrew Goldberg and Chris Harrelson, 2005) is called ALT, for A*, landmarks and the triangle inequality.
Five waves in advance, and the search looks at 20 stations instead of 141, and at 19 instead of 255. The straight line from the previous trip gave 56 and 78: distances along the tracks are far better hints.
Hierarchies. Someone driving from New York to Chicago doesn’t wander the side streets of Cleveland: they get on the interstate and get off near the destination. The method of contraction hierarchies (Robert Geisberger, Peter Sanders and colleagues, 2008) does this rigorously. The intersections are ranked by “importance” and removed one at a time, starting with the least important. When an intersection is removed, a shortcut edge is added between its neighbors if the shortest path between them went through it, so the distances among the remaining intersections don’t change. A query is two Dijkstra waves, one from the start and one from the goal, which climb only toward more important intersections and meet at the top, “on the interstate.” Each wave sees hundreds of vertices instead of millions, and the answer is exact.
The fastest known methods answer a query on the road network of a whole continent in a few hundred nanoseconds, and take fresh traffic into account in under a second (these figures come from a 2016 survey by Hannah Bast and colleagues). Traffic changes the edge weights every minute, so the preprocessing is split in two: a long part that depends only on the road map, and a quick part that recomputes the weights. Companies don’t usually say which methods a particular navigation app uses, but all of these principles are described in open papers.
A navigation app doesn’t try out routes; there are far too many. It sees the map as a weighted graph (Chapter 19) and runs Dijkstra’s wave across it: each time it expands the nearest intersection not yet settled, and it gets that nearest one from a heap (Chapter 18) in logarithmic time. This greedy step is safe, by a proof of the same kind as Kruskal’s correctness in Chapter 23, so the path found is a shortest one, and the work is almost linear in the size of the map. The A* heuristic turns the wave toward the goal and loses no accuracy as long as it never overestimates the rest of the way. The biggest speedup comes from preprocessing: once, in advance, the map is turned into a hierarchy of roads with shortcuts and into tables of distances to landmarks. After that, a query across the road network of a whole continent looks at hundreds of intersections instead of millions and takes a fraction of a millisecond.
Tasks
Four tasks, four versions of the navigation app. Each has a big test with a stopwatch, and an edge case that is easy to trip over.
The graph is given as a dictionary: graph[u] is a list of pairs (v, w), an edge from u to v of weight w >= 0. Write dijkstra(graph, start), which returns a dictionary of the shortest distances from start to all reachable vertices (unreachable ones must not be in the dictionary). Careful: a vertex may appear only as the end of an edge and have no list of its own in graph. The tests have 100,000 vertices and 400,000 edges.
A heap of pairs (estimate, vertex) and a dictionary dist. When you take a pair out, skip it if its estimate is worse than the one already known.
Get a vertex’s neighbors with graph.get(u, []); then vertices without a list won’t raise a KeyError.
Only pairs with a number in front go into the heap, so vertices are never compared with each other, and they can be anything, tuples or strings. Loops and parallel edges don’t bother the algorithm: a loop never improves an estimate, and of several parallel edges the lightest one wins.
The vertices are numbered 0 to $n - 1$, and the edges are triples (u, v, w): from u to v with weight w, which may be negative. Write bellman_ford(n, edges, start), which returns a list of distances from start (math.inf for unreachable vertices), or None if a cycle of negative length is reachable from start. A negative cycle that can’t be reached from the start doesn’t affect the answer.
$n - 1$ rounds: in each, go through all the edges and relax them. Skip an edge if its start is still unreachable: inf + (-5) is still inf, but skipping is clearer and faster.
After $n - 1$ rounds, run one more as a check: if any estimate decreases, return None. If a round passes with no changes before that, you can stop right away.
The check round catches only cycles reachable from the start: vertices that can’t be reached keep an infinite estimate, and their edges are never relaxed. Stopping early doesn’t change the worst case, $O(nm)$, but on most graphs it saves nearly all the rounds.
The map is a list of strings of equal length: '.' is road (entering the cell costs 1), '~' is swamp (costs 3), '#' is wall. You can move to the four neighboring cells. Write astar(grid, start, goal), where start and goal are pairs (row, column). Return a pair: the least cost of a path (or None if there is no path) and the number of cells the search took out of the heap and processed. The tests check the cost and one more thing: on a big map without walls, the search must process only a small fraction of the cells, which Dijkstra can’t manage.
The heuristic is the Manhattan distance: abs(r - goal[0]) + abs(c - goal[1]). It never overestimates: every step moves one cell and costs at least 1.
Keep triples (g + h, -g, cell) in the heap. When you take a cell out, skip it if it has already been processed; otherwise increase the counter and, if it is the goal, return the answer.
Why -g? On an open map, every cell of the rectangle between the start and the goal has the same sum $g + h$. If ties go to the cell with the smaller $g$, the search floods the whole rectangle, like Dijkstra. If they go to the larger $g$, that is, to the cell closer to the goal, it heads for the goal almost directly.
The second number in the triple breaks ties on the sum $g + h$: with equal sums, the cell that is already farther along comes out first. Without it, ties would be broken by the cells themselves, which is also correct, but on an open map the search would process the whole rectangle between the start and the goal. The answer doesn’t depend on how ties are broken; only the amount of work does.
Write fastest(graph, names, a, b): graph and names are what load_metro(minutes=True) returns, and a and b are station names as a passenger sees them: 'Kievskaya', not '4:Kievskaya'. One name can belong to several stations on different lines, and you may start and finish at any of them. Return a pair: the time in minutes and the list of station ids along the route. If there is no station with such a name, return None.
Put all the stations named a into the heap at once, each with an estimate of 0: it is the same as a dummy start with free edges to them.
Stop as soon as any station named b is settled. Recover the route from prev; for the starting stations, prev is None.
If a and b are the same name, the answer is 0 minutes and a single station: the first to come out of the heap is a starting station, and it is already a goal. The idea of putting many starts into the heap at once works whenever you can begin from several places: the nearest fire station, the nearest store.
What next
The navigation app is ready, but it answers one passenger’s question. A dispatcher asks a different one: thousands of trucks run over a road network, every road has its own limit on how many vehicles it can carry per hour, and the question is no longer “how do I get there” but “how much gets through in all, and where is the bottleneck.” How much freight can a whole road network carry? In the 1950s military analysts pored over a railroad map with this question in mind, and the answer turned out to be tied to another question: how to cut that network. That is the subject of the next chapter.