How Google Maps Finds the Shortest Path: Dijkstra's Algorithm

How does Google Maps know, out of millions of possible routes through a city, which one gets you there fastest?

It's not magic, and it's not brute force either. It's a single, elegant idea from 1956, dreamed up by a computer scientist named Edsger Dijkstra during a coffee break, without even a pencil and paper.

The idea: treat the map like a pond. Drop a stone at your starting point. Watch the ripples spread. The ripple reaches nearby streets first, then farther ones, always in order of distance. By the time the ripple reaches your destination, you already know the shortest way there.

That's Dijkstra's algorithm. Let's build it from scratch.

Why not just try every route?

Your first instinct might be: just check every possible path and keep the shortest one. That works, technically. But watch what happens as the map grows.

A tiny grid of streets already has dozens of routes between two points. A real city has thousands of intersections. The number of possible paths doesn't grow steadily, it explodes, because at every intersection you multiply your choices by however many streets branch off.

Checking every route isn't slow, it's impossible. Google Maps would still be "thinking" long after you'd already walked there. We need a smarter approach, one that never has to look at most of the map at all.

Water finds the shortest way by itself

Here's the trick. Forget computers for a second. Imagine your city is a network of canals, and every street segment takes a certain number of minutes to cross. Now pour water in at your starting point.

Water doesn't know where it's going. It just spreads, and it spreads at a constant rate. Because of that, water reaches every intersection in exactly the order of its true distance from the source. The nearest corner gets wet first. The farthest corner gets wet last. There's no way for water to "cheat" and arrive somewhere out of order, since it's always advancing at the same rate everywhere at once.

Watch the ripple in the graph above. Notice that a node only lights up once the wave physically arrives, and the number stamped next to it is the exact travel time from A. That number never changes once it's set. That's the whole algorithm, just translated into water.

The rule: always expand the closest place first

Computers can't pour water, so Dijkstra's algorithm fakes it with a very simple rule, repeated over and over:

1. Look at every place you can currently reach (the "frontier").
2. Pick whichever one is closest to the start.
3. Mark it as done, its distance is now final.
4. Update the distances to its neighbors, in case going through it is a shortcut.
5. Repeat.

That's the entire algorithm. No trick, no magic, just "always take the closest next step." We write step 4, updating a neighbor's distance, as a small formula called relaxation:

In plain English: the best known distance to $v$ is either what we already had, or the distance to $u$ plus the cost of the edge from $u$ to $v$, whichever is smaller. Do this for every neighbor, every time you settle a new node.

The "look at everything reachable, grab the closest" step is handled by a data structure called a priority queue, basically a sorted waiting line where whoever has the smallest distance gets served next.

Step through it above. Watch the queue on the right, it always contains only the frontier, the places you can reach but haven't finalized yet. And notice it always hands over the smallest one. That's not a coincidence, it's the entire strategy.

Why greedy doesn't backfire

Here's the part that should bother you a little. The algorithm commits to a node's distance the moment it's popped from the queue, and never revisits it. That seems risky. What if a shorter path shows up later?

It can't, and here's why: every edge weight is non-negative. When we pop the closest node in the frontier, every other path to it would have to go through some other frontier node first, and every other frontier node is already farther away. Going through something farther can't produce something closer, not when distances only add up. So the closest node in the frontier really is finished, permanently.

That safety net depends entirely on weights never being negative. Break that assumption, and the whole guarantee collapses.

Drag that weight negative. Once it dips low enough, a longer-looking route through B secretly becomes cheaper, but Dijkstra already locked in A's distance before it ever discovered that shortcut. The algorithm doesn't go back and check. That's precisely why real routing engines never treat any road as having negative travel time.

From street maps to real GPS routing

Everything so far has used a small hand-drawn graph, but a real map works exactly the same way, just at a much bigger scale. Every intersection is a node. Every road segment is an edge. And the "weight" isn't distance in miles, it's whatever Google Maps actually wants to minimize: usually travel time, which factors in speed limits, and real-time traffic.

That last part matters. A road that's physically short but jammed with traffic gets a high weight. A longer road that's wide open gets a low one. Dijkstra doesn't know or care about geography, it only cares about the numbers on the edges, which is exactly why it can route you around a traffic jam without "seeing" the jam at all.

Click anywhere on the grid above to set a new destination. The red block is heavy traffic, notice how the algorithm routes around it instead of plowing straight through, even though going straight through looks shorter on the map. Cost, not distance, is what Dijkstra actually optimizes.

The short version

Dijkstra's algorithm finds the shortest path by always expanding the closest unfinished place first, the same way water spreads outward from a source at a constant rate. Because road weights are never negative, once a place's distance is finalized, no later discovery can ever beat it, so the algorithm never has to backtrack. A priority queue keeps track of the frontier so the "closest next step" is always instantly available, without ever checking most of the map.

That's what's running, thousands of times a second, every time you type an address into Google Maps.

All visualizations are interactive React components running entirely in your browser. The graph traversal, wavefront timing, and grid pathfinding all use the same Dijkstra implementation shown in this post, computed live as you interact. No libraries beyond React.