- Current
- In the queue
- Final
- Path
- Straight-line guess
A* search
A* search finds a shortest path from a start to a goal, like Dijkstra's algorithm, but it knows roughly where the goal is. Every node gets a guess of the distance still to go, the straight line to the goal, and the search always continues from the node with the lowest distance so far plus that guess. Click a node to start from it, pick a goal, and step through to see the search head towards the goal and leave whole corners of the graph untouched. Press Play to watch the search, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Click a node to make it the start; switch the click to Goal and click another node to make it the goal. The number on each edge is its length, the number on each node its distance so far, and the dashed line the straight-line guess of the distance still to go. The row under the graph is the queue, lowest score first, with each score: the distance so far plus the guess. New graph makes another graph; choose how many nodes and edges it has. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Click a node to make it the start. Switch the click to Goal and click another node to make it the goal.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere in the search.
- Watch the scores in the queue and the dashed straight-line guess. At the end, compare the nodes A* needed with Dijkstra's algorithm.
How A* search works
Give the start distance 0 and put it in a queue. Each node in the queue has a score: its distance so far plus a guess of the distance still to go. Repeat: take the node with the lowest score, and mark its distance final. If it is the goal, stop. Otherwise, for each neighbour that is not final, add the edge's length to the node's distance; if that is shorter than the neighbour's distance so far, lower it, remember the node as the way there, and put the neighbour in the queue with its new score.
Why the guess must never be too long
A* finds a shortest path as long as the guess never says the goal is farther than it really is: an admissible guess. The straight line is one, because no road between two places is shorter than the straight line. A guess that is too long can make A* skip the best route; a guess of 0 everywhere turns A* into Dijkstra's algorithm, which is safe but looks in every direction. The better the guess, the fewer nodes A* needs. In the app, every edge is as long as it is drawn, rounded up, so the straight line is a safe guess.
Frequently asked questions
What is A* search?
A pathfinding algorithm that finds a shortest path from a start to a goal. It works like Dijkstra's algorithm, but orders its queue by the distance so far plus a guess of the distance still to go, so it heads towards the goal instead of spreading out in every direction.
What is an admissible heuristic?
A guess of the distance to the goal that is never longer than the real shortest distance. With an admissible guess, A* always finds a shortest path. The straight-line distance on a map is the classic example.
Is A* faster than Dijkstra's algorithm?
Usually, when you need the way to one goal and have a good guess: A* finalizes fewer nodes, because nodes that lie away from the goal get high scores. With a guess of 0 it does exactly what Dijkstra's algorithm does. Dijkstra's algorithm is the better choice when you need the distances to every node.
Where is A* used?
In video games to move characters around obstacles, in route planners, in robot motion planning, and in puzzle solvers such as the 15-puzzle, where the guess counts how far the tiles are from their places.
Is my graph sent anywhere?
No. The graph is made and searched in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor