Shortest path

Guess the rest of the way

A* keeps a frontier: junctions it has reached but not yet explored. For each one it knows g, the cost of the best way found from A, and guesses h, the cost still to go to B. It always explores the junction with the smallest f = g + h next, so it leans towards B instead of flooding outwards like Dijkstra.

Admissible means the guess never overestimates. Then the first time A* reaches B, nothing it skipped could have been shorter, so the route is guaranteed to be the shortest. The straight line is admissible for distance, because no street is shorter than a straight line. For fastest time the page divides the straight line by the fastest speed on the map, so the guess stays low even on a motorway, but it is weak and A* saves less.

The weight w scales the guess. At 0 it is Dijkstra, at 1 it is A*, and above 1 it trusts the guess more and races for B like greedy best-first. With an admissible guess the route is never more than w times the shortest, and usually much closer. An overestimating guess gives up that promise.

One extra term turns a blind flood into a search that knows roughly where it is going.

Why sat-navs and games use it

A sat-nav has to answer in milliseconds on a road network of millions of junctions. A good guess keeps the search to a narrow band towards the destination; real ones add precomputed tricks such as landmarks and contraction hierarchies, which are just better guesses and shortcuts.

Games run A* for every unit, many times a second, usually on a grid. There Manhattan distance is the natural guess, and a weight a little above 1 is a common trade: a slightly worse path for far less work.