A* search
Dijkstra's algorithm finds the shortest way to a goal, but it searches in every direction at once, even away from the goal. A* search adds one piece of knowledge, a guess of how far the goal still is, and suddenly the search heads straight for it.
The idea
When you look for a route on a map, you do not explore roads that lead away from your destination with the same care as roads that lead towards it. A* search does the same. Every node gets a score: the distance from the start so far, g, plus a guess of the distance still to go, h. The search always continues from the node with the lowest score, so nodes that lie towards the goal come first.
Step by step
Give the start distance 0 and put it in a queue with score h(start). Repeat: take the node with the lowest score, and mark its distance final. If it is the goal, stop: following the remembered nodes back gives the path. Otherwise, for each neighbour that is not final, work out its distance through this node. If that is shorter than its distance so far, lower it, remember this node as the way there, and give the neighbour the score of its new distance plus its guess. When two scores are equal, taking the node with the smaller guess first usually reaches the goal sooner.
An example
Take a start A and a goal D. A–B is 2 long and B–D is 2, while A–C is 1 and C–D is 5. The straight-line guesses to D are 3 from A, 2 from B and 3 from C. A starts with score 0 + 3 = 3. Taking A gives B the score 2 + 2 = 4 and C the score 1 + 3 = 4. With a tie, A* takes B, the node with the smaller guess, and B gives D the score 4 + 0 = 4. D now has the lowest score with the smallest guess, so it is taken: the shortest path is A → B → D, of length 4, and C, which leads the wrong way, is never finalized. Dijkstra's algorithm would have finalized C first, because it is the nearest node to A.
A good guess
The guess must never be longer than the real distance to the goal; such a guess is called admissible, and with it A* always finds a shortest path. The straight line is admissible because no route is shorter than a straight line. If the guess also never drops by more than an edge's length from one node to the next, it is consistent, and no final node ever needs to be looked at again. The closer the guess is to the truth, the fewer nodes A* needs. A guess of 0 is admissible but useless: A* then becomes Dijkstra's algorithm. A guess that is too large makes A* faster but can miss the shortest path.
History and uses
Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute published A* in 1968, while working on Shakey, one of the first mobile robots. Their earlier versions were called A1 and A2; the star marked the version they proved to be optimal. Today A* moves characters around obstacles in video games, plans routes and robot movements, and solves puzzles such as the 15-puzzle, where the guess adds up how far each tile is from its place.
Explore it
Open the app and press Step. The numbers on the edges are their lengths, which here match how long they are drawn, and the dashed line shows the straight-line guess to the goal. The queue under the graph lists the nodes by score, lowest first. When the goal is final, the status line compares how many nodes A* finalized with how many Dijkstra's algorithm would have needed. Try a goal in a far corner of a large graph to see the biggest difference.
Frequently asked questions
What does the star in A* mean?
Hart, Nilsson and Raphael first described algorithms they called A1 and A2. A* ("A star") was the version they proved to find a shortest path with the fewest nodes expanded among comparable algorithms using the same guess, when the guess is consistent.
What is the time complexity of A*?
In the worst case, with a useless guess, A* does the same work as Dijkstra's algorithm: O((V + E) log V) with a binary heap. With a good guess it finalizes only a fraction of the nodes, which is why it is fast in practice.
What makes a good heuristic for A*?
It should be quick to compute, never overestimate the real distance, and be as close to it as possible. On a grid where you can only move up, down, left and right, the Manhattan distance is a common choice; on a map, the straight-line distance.
What if the heuristic overestimates?
Then A* may return a path that is not the shortest, because it can finish before looking at the better route. Some programs do this on purpose (weighted A*) to trade a little path quality for much speed.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try A* search