How does sat nav find the fastest route? Pathfinding explained
Updated · Plixoo
Short answer
Sat nav finds a route with a pathfinding algorithm. It treats the road map as a graph - junctions joined by roads, each road with a travel time - and searches outward from where you are. Dijkstra's algorithm explores junctions in order of how far they are from the start, which guarantees it finds the quickest route. A*, pronounced 'A star', adds a guess at the remaining distance, such as the straight-line distance to the destination, so it explores roads that head the right way first and finds the same quickest route while checking far fewer roads. Real sat navs add precomputed shortcuts and live traffic on top.
A map is a graph
To a computer, a road map is a set of points (junctions) joined by lines (roads). Each line has a cost: its length, or the time it takes to drive. Finding the fastest route means finding the path from one point to another with the smallest total cost. Game worlds work the same way, usually as a grid of squares where each square joins its neighbours.
Breadth-first search: the flood
The simplest reliable method spreads out from the start like water: first every square one step away, then every square two steps away, and so on. The first time the flood reaches the goal, it has found a shortest path, because it checked every shorter distance first. The drawback is that it explores in every direction at once, including directly away from the goal.
Depth-first search: the maze runner
Depth-first search picks a direction and keeps going until it hits a dead end, then backs up and tries the next option. It uses little memory and will find a way out of a maze eventually, but the first path it finds is often a long, winding one. It does not guarantee the shortest route.
Dijkstra and A*: searching smarter
Dijkstra's algorithm, published by Edsger Dijkstra in 1959, is the flood adapted for roads of different lengths: it always extends whichever unexplored junction is currently closest to the start. A*, from 1968, adds a heuristic, an estimate of how far each junction still is from the goal. As long as that estimate never overestimates, A* still finds the best route, but it spends its effort on roads pointing the right way.
On a big map the difference is enormous. The flood checks everything within your trip's distance in every direction; A* mostly checks a corridor between you and the destination.
- Breadth-first search: shortest path on equal-cost grids, explores everywhere
- Depth-first search: finds a path, not necessarily the shortest
- Dijkstra's algorithm: shortest path when roads have different costs
- A*: the same shortest path as Dijkstra, usually after exploring much less
Games mentioned here
Frequently asked questions
What algorithm does Google Maps use?
Mapping services do not publish their exact methods, but route planners at that scale are built on the ideas behind Dijkstra's algorithm and A*, combined with precomputed shortcuts through the road network and live traffic data so a route across a country can be found in milliseconds.
What is the A* algorithm in simple words?
A* is a route-finding method that, at every step, extends the path that looks best when you add the distance already travelled to a sensible guess of the distance still to go. That guess steers it toward the goal, so it finds the shortest route while exploring much less of the map.
How do characters in video games find their way?
Most use A* on a simplified map of the level, either a grid or a 'navigation mesh' of walkable areas. The path is then smoothed so the character does not walk in visible zigzags.
Is breadth-first search the same as Dijkstra's algorithm?
They are the same idea when every step costs the same. Dijkstra's algorithm generalises breadth-first search to maps where different roads have different lengths or travel times.
More guides
The best free online games you can play with no download
Twelve browser games worth your time, sorted by what you actually want out of them.
How to play 2 player games on one phone
No second device, no accounts, no lobby. Just one screen and two people taking turns.
Are browser games safe for kids? What to actually check
The risks in kids' games are rarely the games. Here is what to actually look at.
How to get better at puzzle games
Most puzzle games have a technique. Knowing it beats being clever every time.
Why classic arcade games are still good
Five games from between 1972 and 1984 that nobody has improved on.
What to play when you are bored and cannot decide
Skip the scrolling. Answer two questions and start playing.
How does AI work? Explained for kids (and everyone else)
No metaphors about brains. What an AI actually does, why it gets things wrong, and how to show a child rather than tell them.
The best coding games for kids, and what each one actually teaches
Coding games are good at the part tutorials skip. Here is what each one teaches and where they stop being enough.
How computers actually work, from switches upward
Four layers, bottom to top. None of them are complicated, and together they are the whole machine.
How to make a strong password (and why most advice is wrong)
Length beats symbols, wordlists beat cleverness, and the advice on most sign-up forms is a decade out of date.
How to solve the Tower of Hanoi, and why it teaches recursion
The three-step method that solves any size of tower, the by-hand shortcut, and the idea behind it.
How to spot a phishing message: the warning signs
The seven signs that give a scam message away, and the one habit that beats almost all of them.
How to learn touch typing: a simple plan that works
Where your fingers go, what to practise first, and how long it really takes.
Morse code alphabet: the chart, the rules and how to learn it
Every letter and number, the timing rules, and the quickest way to learn it by ear.