How GPS Finds the "Fastest" Route: Dijkstra's Algorithm

A road map is a graph — intersections are nodes, roads connecting them are edges, and each road's driving time is that edge's weight, exactly the setup described in this site's "what a graph actually is." Finding the fastest route from home to a destination is really the question "what's the lowest-total-weight path through this graph," and Dijkstra's algorithm is the classic, still-widely-used way to answer it without trying every possible route.

The algorithm keeps a running scoreboard: for every intersection, the cheapest total travel time found so far to reach it from the start. Every intersection begins at "infinity" (unknown) except the starting point, which begins at zero. The algorithm repeatedly picks the not-yet-finalized intersection with the lowest known score, locks that score in as final, and then checks every road leading out from it — if going through that intersection would make some neighboring intersection's known score cheaper than what's currently on the scoreboard, it updates the scoreboard with the better number.

That single repeated step — lock in the cheapest unfinished intersection, then see if it improves anything reachable from it — is the entire algorithm. It never has to consider every possible route through the map, because once an intersection's score is locked in, no route arriving later could possibly beat it: any path found afterward has already accumulated at least as much cost getting to intersections that were, by definition, more expensive to reach.

This is also exactly why Dijkstra's algorithm needs every edge weight to be non-negative — no roads with a negative driving time. The "once locked in, never beaten" guarantee only holds if adding another road to a path can never lower the total cost, which is obviously true for real travel time but isn't true for every graph problem, which is why some other algorithms exist specifically to handle graphs where a weight can go negative.

Real GPS software layers a lot on top of this basic idea — current traffic conditions changing edge weights in real time, one-way streets as directed edges, additional shortcuts that avoid checking every intersection on a continent-sized map — but the core logic your phone runs dozens of times on a single trip, every time traffic changes and it "recalculates," is still this same repeated step: find the cheapest known way to somewhere, lock it in, and see what that unlocks.