This is how Google Maps' algorithm finds you the fastest route in just seconds and it's jaw-dropping to see

Have you ever wondered how Google Maps’ algorithm finds you the fastest route in just seconds?

There are more than 64 million intersections across North America’s road network, creating an almost unfathomable number of possible routes.

Checking every single one would take longer than you could possibly imagine, yet navigation apps can calculate a route almost instantly.

The secret comes down to decades-old math, clever shortcuts, and some seriously smart algorithms.

Google Maps’ algorithm started with a 20-minute idea

The car navigation app story starts in 1956 with Dutch computer scientist Edsger Dijkstra, who was looking for a mathematical way to demonstrate the power of an early computer called ARMAC.

During a shopping trip in Amsterdam, Dijkstra came up with a problem that ordinary people could understand: finding the shortest route between Rotterdam and Groningen.

His solution became known as Dijkstra’s algorithm, and the basic concept was remarkably straightforward.

Rather than checking every possible journey, the mathematical algorithm assigned a cost to each location based on the shortest route discovered so far.

It started with a cost of zero at the starting point and then explored nearby locations, always moving to the one with the lowest known cost, and if it found a shorter way to reach somewhere, it updated the cost and continued.

This guaranteed that it would eventually find the shortest route without having to test every possible combination.

View this post on Instagram

A post shared by Explain (@explain)

The algorithm was reportedly designed in around 20 minutes and went on to become one of the most important algorithms in computer science.

But there was a problem, but while Dijkstra’s algorithm was incredibly fast for its time, it wasn’t fast enough to deal with modern road networks and millions of simultaneous navigation requests.

The fastest route comes from making the map smaller

One improvement is A*, which adds a clever shortcut that estimates how close each location is to the destination.

Instead of spreading out in every direction, the algorithm can prioritize locations that appear to be heading toward the target, which dramatically reduces the amount of the map it needs to explore.

But road networks have another major advantage: they have a natural hierarchy.

If you’re driving across the country, whether you use Google Maps or not, you’re probably going to use small roads to reach a major highway, stay on that highway for most of the journey and then return to local roads near your destination.

A technique called a customizable contraction hierarchy takes advantage of exactly this.

The system ranks intersections according to how important they are to the wider network like a major interchange connecting multiple highways is extremely important, while an intersection at the end of a quiet cul-de-sac isn’t.

It can then create mathematical ‘shortcuts’ between important points because these aren’t real roads, but they allow the algorithm to skip over huge sections of the network while still preserving the information needed to find the correct route.

In a test featured in this video by Veritasium, this approach calculated a route across North America in around 200 microseconds, or just 0.0002 seconds.

That’s around 35,000 times faster than Dijkstra’s algorithm in the same experiment, while examining roughly 1,450 nodes instead of potentially millions.

The exact technology used by Google Maps isn’t public, so there’s no guarantee it uses this precise algorithm, but we can be pretty sure.

But the demonstration gives an inside glimpse at what’s happening behind that little blue line on your phone when you look up where the closest Walmart is.

What looks like a simple route is actually decades of computer science, enormous amounts of processing and some shortcuts – all happening before you’ve even had time to wonder why Google wants you to take that weird back road behind the deli.

Dig deeper into the Google Maps vs. Waze vs. Apple Maps debate

These three related stories take a closer look at the features and real-world differences between Google Maps, Waze, and Apple Maps — helping you decide which navigation app deserves a place on your phone.

Man drives over 1,000 miles to test out Apple Maps vs Google Maps for an entire month and reveals which is best

A journalist spent an entire month using both navigation apps across his daily commute and weekend road trips, putting them through traffic, unfamiliar roads and plenty of tricky turns.

People are saying Google Maps just left Apple Maps another five years behind with its biggest upgrade in years

In yet another addition to the ongoing navigation app rivalry saga, Google Maps has brought in a huge update that’s apparently blown its competition out of the water.

Man compares Waze and Google Maps and ends up realizing it’s not even a debate as one is too far ahead

This software writer drew direct comparisons between the two navigation apps, trying to keep things as ‘scientific’ as possible.