• [Derek] Say you wanna drive from New York to San Francisco. How could you calculate the absolute shortest path? There are over 64 million intersections in the North American road system, so a simplified estimate gives around 10 to the 220 possible routes. Even if you could check a billion routes per second, testing all of them would still take over 10 to the 200 years. And this isn't just a problem for navigation software. Any independent system like a robot or a video game character that needs to navigate a maze, or obstacle course faces this same problem. And yet, Google or Apple Maps will find you the route in only four seconds. So how is that possible? Well, we teamed up with the channel 2swap, who creates incredible simulations and animations to show you step by step, how these algorithms work. They trace their origins back to a shopping trip in Amsterdam in 1956. (jaunty music) Edsger Dijkstra needed a problem. He was working on software for ARMAC, an early computer developed at the mathematical center in the Netherlands. And it was almost ready to debut. But at the time, the general public considered computers to be practically useless. So useless, in fact, that Dijkstra ran into issues filing his marriage license.
• [Casper's Dijkstra Impression] Dutch marriage rights require you to state your profession, and I said that I was a programmer. But the municipal authorities of the town of Amsterdam didn't accept it on the ground that there was no such profession. And believe it or not, that under the heading "profession," my marriage act shows the ridiculous entry, "theoretical physicist."
• [Derek] And so Dijkstra was looking for a specific demo to prove just how powerful ARMAC was, even to the layperson.
• ['Dijkstra'] The problem of course, is that for a demonstration for non-computing people, you have to have a problem statement that non-mathematicians can understand. And they have to understand the answer.
• [Derek] And during that shopping trip, he thought of the perfect problem.
• ['Dijkstra'] What's the shortest way to travel from Rotterdam to Groningen?

• [Derek] In other words, a shortest path algorithm. Here's a simplified graph of the Netherlands. The nodes represent the cities, and the edges connecting them are the roads. The simplest way to find the shortest path from Rotterdam to Groningen looks like this. Starting from Rotterdam, we're first going to explore all its neighbors looking for Groningen. Since Groningen isn't one of these neighboring nodes, we'll mark Rotterdam as explored, and keep searching. So now we'll branch out from these four nodes to explore all of their neighbors. And we keep branching out this way, exploring all neighboring nodes, until we stumble upon Groningen. This algorithm is known as Breadth-First Search. It will always find the shortest path because it checks all nodes one step away, and then two steps away, and so on. So if there were a path from Rotterdam to Groningen in four steps, we would've found it on the fourth iteration, but we didn't. So the shortest path must be five steps. But there's a problem with this approach. I mean, the algorithm considers all these roads to be the same length, which is obviously not true. So let's add weights to represent distances between these nodes. Now the shortest path is much harder to figure out. So Dijkstra needed a better method.
• ['Dijkstra'] One morning I was shopping in Amsterdam with my young fiance, and tired, we sat down on the cafe terrace to drink a cup of coffee. And I was just thinking about whether I could do this.
• [Henry] His idea was this. First he wanted to keep track of the shortest distance from the source to each node. This is also known as its cost. His goal, well, if he could find the shortest path from the source to one node, then he could build up other shortest paths starting from this new node, and then the next, and on and on. Now, the cost of the starting node was zero. But since he hadn't actually explored the rest of the graph yet, he set all the other nodes to a cost of infinity. Then just like breadth-first search, Dijkstra started from the source, and explored each of its neighboring nodes. At every step he'd ask, "Is the current path to this node the shortest we've seen so far?" For example, this edge only has a weight of one, while the node's current cost is infinity. So this path is the shortest yet to that node. So Dijkstra updated its cost to one. Likewise, these nodes were updated to three, two, and four. After checking all of Rotterdam's neighboring nodes, Dijkstra marked it as explored. Then since this node had the lowest cost out of all the unexplored nodes, Dijkstra explored it next. Like before, he checked each of its edges to reduce the neighbor's costs. Dijkstra could update this neighbor from infinity down to six, a total path length of five plus one, but he couldn't update this one. The current path has a cost of five, but the nodes' cost was three. That meant there was already a shorter path, this one directly from the source. So there was no need to update the cost. The next node to explore is this one with a cost of two, which would update its neighbor to five. Then this one with a cost of three would update its neighbors, and so on. Sometimes Dijkstra had to update a node's cost a few times. For example, he first reached this node through this path with edge weights four, and then three, for a total cost of seven. But later he found this path was cost six. So he updated the nodes cost again. (gentle music) The first time Dijkstra reached Groningen, it had a cost of 19. But it didn't have the lowest cost out of all the unexplored nodes. There was still this node with a cost of 16, which could be hiding a shorter path to our goal. So he continued exploring nodes in cost order, and found this path with cost 18. Now, out of all unexplored nodes, Groningen had the next lowest cost. So Dijkstra was confident that he'd found the shortest path. Here's why. If the lowest cost among the unexplored nodes is 18, then Dijkstra must have explored all the paths with cost 16, 14, 13, every path less than 18. And none of those paths reached Groningen. It's just like breadth-first search, searching every step away from the source. By exploring from lowest to highest cost, Dijkstra's algorithm guaranteed the shortest path to any target.
• ['Dijkstra'] It was a 20-minute invention. I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities.

• [Derek] During ARMAC's official inauguration in 1956, Dijkstra asked the audience members for two towns on a simplified map of the Netherlands. ARMAC then printed the shortest route town by town. It ran perfectly. The computer was such a success that the center immediately started the next generation. And as for his algorithm, well, it just sat in his papers for years. Algorithms weren't respectable enough for mathematics journals, and there weren't very many computing journals yet. But in 1959, he published his work in Numerische Mathematik, or Numerical Mathematics, a brand new German journal that needed some help getting established. And that was the beginning.
• ['Dijkstra'] Eventually, that algorithm became, to my great amazement, one of the cornerstones of my fame. I found it in the early '60s in a German book on management science, Das Dijktra'sche Verfahren. Suddenly there was a method named after me. Dijkstra's algorithm is still regarded as one of the most elegant, shortest path algorithms. But it isn't good enough for Google Maps. Let's say I want to get from Newark Airport in New Jersey over to the Central Park Zoo. First, Dijkstra's algorithm checks all the 10-kilometer journeys, and then all the 20 kilometer journeys, and so on until it reaches all the 28 kilometer journeys, which includes the zoo. The search frontier covers over 65,000 nodes, and includes places that are way off, like Staten Island, and large swaths of New Jersey. But even though it searched in a illogical directions, the runtime was about a 10th of a second, which is incredibly fast. ...
• [Derek] Now less than 100 milliseconds seems pretty fast. So what's the problem? Well, things slow down a lot with bigger and bigger graphs. Like the North America network. One way we can compare search algorithms is by their average query speed. First we pick lots of random points. Then we run Dijkstra's algorithm on each pair of points and average all the runtimes. On the North American network, a well-tuned Dijkstra takes around seven seconds per path. And for a lot of these searches, the algorithm has to explore most of those 64 million nodes. ...
• [Henry] And while Google has a lot of servers, there's a limit. If we want Google Maps to run in a couple of seconds, we actually need the algorithm to run in less than a millisecond, something 7,000 times faster than Dijkstra's.

(whooshing sound) Well, one problem with Dijkstra's is it searches in the opposite direction of the target. So if we know the rough direction, is there a way that we can punish a illogical route? Let's go back to our problem, getting from Newark to the Central Park Zoo. We'd like to prioritize nodes that are closer to the zoo. So using longitudes and latitudes, we can easily calculate the straight line distance between any node and our target. We'll order the nodes by their cost, plus this straight line distance. A great way to visualize this comes from the channel Polylog. We can represent each node's straight line distance to the target as its height, so the graph stretches into 3D space. The further a node is from the zoo, the higher it is. So the algorithm penalizes moves that climb up the graph. That way nodes in the opposite direction aren't explored early on. So while Dijkstra's search frontier spreads out in all directions, this modified Dijkstra's, also called A-star, immediately heads toward the zoo. It only checks around 7,000 nodes, which is almost a 10 times improvement over Dijkstra's. And by changing this penalty, also called a heuristic, we can tweak how aggressively A-star targets the zoo. ...

• If you wanna go for the shortest path in the sense that shortest geographic distance, you will gain some advantages using A-star, compared to Dijkstra. If you go for travel time, A-star, from my experience, loses against a well-tuned Dijkstra. You explore fewer nodes, but not that many. But you now also have to evaluate quite a few heuristics that you would not need to evaluate when doing pure Dijkstra. And those heuristic contain a nasty square root computation.

• [Henry] On our New York City graph, Dijkstra's algorithm explored around 9.5 times more nodes than A-star, to find the shortest path by distance. But if we switch that to the shortest travel time, the number of nodes A-star explores triples, while Dijkstra only increases by 10%. And it only gets worse on larger graphs. So Google Maps need something better that works well for travel time. What if we ran the search in both directions? From the source to the target, and from the target to the source? If two points are a distance R away, Dijkstra searches most of the nodes roughly within a circle of area pi R-squared. But with two searches, the frontiers will overlap around R over two, and cover an area of half pi R-squared, half that of the single search. And depending on the graph, it can sometimes be better than half. A basic Dijkstra search from Carnegie Hall to Wall Street explored over 7,200 nodes. But a bi-directional Dijkstra explored a little over 2,600 nodes, close to a three times improvement. But even a bi-directional search doesn't take advantage of the logic built into road networks.
• They still do things that you wouldn't necessarily conceive as a good idea, right? ...
• When I think about how to get from one place to another, I know that I'm probably gonna meander around some local roads, then hop on a highway, and then when I'm close to my destination, I'm gonna hop off the highway and meander around some more local roads. There's a hierarchy to road networks, but these algorithms can't take advantage of them. ...
• So here was the basic idea. Surveyors would go out and take notes about a road. ...
• Once it had the maps, GPS would run a bi-directional Dijkstra, but there was a catch. It first searched all the narrow roads within a candidate area. If it didn't find the target, it mapped the path to the next hierarchy, the major local roads. Then search all of the major local roads within the new candidate area. If it still didn't find the target, it moved up again to the highway level. The two searches would overlap at some point, and return the final path. This way, a little pre-processing could reduce the search area and take advantage of the road hierarchy.
• One obvious downside here is that how do you correctly compute those levels of hierarchy? And how can you prove to yourself that they're correct in the sense that you are not missing any shortest paths?

• [Derek] If Google wanted to map the world, they need a better routing algorithm. ...
• The idea is very similar to the manual hierarchies, but with two major changes. First, we'll automatically pre-process our graph to order nodes by how important they are. ...
• [Henry] These are the biggest bottlenecks. Out of all the 64 million plus nodes, these 102 get the highest rank, so the biggest numbers. Now let's find the next most important nodes. ...
• This is called nested dissection. This pre-processing step has two goals. ...
• [Henry] To speed up the runtime, we limit the search space by only moving up the hierarchy. And that's why it's so important to use a bi-directional Dijkstra. ...
• [Henry] Start from the lowest rank. Does this node connect to at least two higher nodes? On this graph, node one connects to three and eight. This is called a lower triangle. And while there's a chance this path is actually the shortest between node three and node eight, our search will never consider it. So we'll add a shortcut between nodes three and node eight. That's just the cost of this lower triangle. ...
• [Derek] This entire algorithm is called a customizable contraction hierarchy. ... Finally, phase three is the actual search. Remember, for a long path on the North American network, a well-tuned Dijkstra needs to explore most of the 64 million nodes and takes around seven seconds per path. For this contraction hierarchy, the query runtime was around 200 microseconds.

• [Derek] ...But if you think about it, its core search is still Dijkstras, a 70-year-old algorithm. Four decades after Dijkstra publishes article, Danish computer scientist Mikkel Thorup said that all theoretical developments in single source shortest paths have been based on Dijkstra's algorithm. And since 2000, many of the newest shortest path algorithms still use bits and pieces of Dijkstras. From variations on contraction hierarchies, all the way to a recent theoretical breakthrough for an even faster shortest path algorithm. All of this, based on a 20-minute invention. Part of Dijkstra's enduring success comes down to just how simple it is. As he said, "Simplicity is prerequisite for reliability." Dijkstra thought deeply about problems before ever touching a pen. Because at the end of the day, it would be a programmer who is accountable for their work, not the machine. ...
• [Derek] So with those two ideas, he hoped to have one lasting legacy. He said, "If 10 years from now, when you're doing something quick and dirty, you suddenly visualize that I'm here, looking over your shoulders, and say to yourself, 'Dijkstra would not have liked this.' Well, that'd be enough immortality for me." So even if you can only control your little corner of the world, you can still make it as elegant and thoughtful as possible. For you, and all the people who come after.