Dijkstra would need 134,000 cores

transcript

The shortest-path algorithm from your textbook is correct. Run it for every driver, and you need 134,000 cores.

Take a benchmark road map of Western Europe. 18 million junctions. A random query with Dijkstra scans 9 point 3 million of them. 2 point 2 seconds, for one route. At 61,000 queries a second, that's the 134,000 cores.

So precompute. Cut the road graph into cells, once. Rivers and railways help. Add shortcuts between each cell's border junctions. Only the shortcut costs depend on traffic. Recompute them from live speeds in zero point three seven seconds. A query uses real roads at its two ends, shortcuts between. One point six five milliseconds.

Dijkstra on every request: about 134,000 cores. With the overlay: about 610.

But here's the catch. Contraction hierarchies are even faster. Zero point one one milliseconds. So why not use them? They bake speeds into their shortcuts. Traffic changes? Contract again. About 2 minutes on 12 cores. Cells and shortcuts just re-cost, in zero point three seven seconds. For live traffic, that wins.

Precompute what depends on the map. Recompute only what depends on traffic.

Full breakdown in the lecture.