Your phone finds the fastest way home in a blink, across a map with millions of road segments. It does not try every route. It uses an idea a Dutch programmer had in 1956: explore outward from the start, always taking the nearest place you have not finished with yet.
Below is a tiny map. Every square costs 1 to cross, except mud, which costs 5. Paint walls and mud, drag the start (S) and goal (G), then slide the bar to watch the search grow one step at a time.
Tip: wall off the goal completely and see what the search does when no route exists.
Give every square a label: the cheapest cost found so far to reach it from the start. The start is 0, everything else is "unknown, maybe infinite". Then repeat one move. Pick the unfinished square with the smallest label and declare it finished. Look at its neighbours. If going through this square gives a neighbour a cheaper label, lower it.
In the demo, the bright squares are finished and the dim rim around them is the frontier of labels still being improved. Notice the shape: on open ground the search spreads as a ring, like ripples on a pond. Mud slows the ripple. Walls bend it.
Here is the trick that makes it work. When a square has the smallest label among all unfinished squares, no later route can beat it. Any other path to that square would have to pass through some unfinished square first, and every unfinished square already costs at least as much. Costs never go negative, so adding more steps can only make a path longer. That is why Dijkstra's method needs costs of zero or more, and why it never has to go back and revise a finished square.
Edsger Dijkstra devised it in 1956 at the Mathematical Centre in Amsterdam. In a 2001 interview he called it a twenty-minute invention, thought up on a café terrace while shopping with his fiancée, and he said he worked it out without pencil and paper. The problem was a demonstration for the ARMAC computer: the shortest route between two cities on a simplified map of 64 Dutch cities. He limited it to 64 so a city number would fit in 6 bits. The paper came out in 1959.
A naive version scans every unfinished square each time to find the smallest label. Keep the labels in a priority queue instead, and a binary heap gives roughly (V + E) log V work, where V is the number of places and E the number of roads. Later work with Fibonacci heaps brought the bound down to E + V log V. Navigation apps go further still, with tricks that skip most of the map, but they grow out of this same idea.
Put a wall with a single gap between S and G and note how many squares get finished before the goal does. Then fill the gap with mud. Does the route go through the mud, or take the long way round? Slide the bar and watch for the moment the two options tie at the same cost.