A*
A* is Dijkstra with the priority changed from g — the cost of the best route found so far — to g plus h, where h estimates the cost still to come. On this grid h is the Manhattan distance to the target: the number of steps needed if there were no walls at all. Every other line of the algorithm is the same as Dijkstra’s, which is why the two can be raced on one clock and compared step for step.
Its frontier
A priority queue, smallest cost-plus-estimate first.
When it is the right choice
Whenever there is a single target and something is known about the geometry: route planning, game path-finding, any search on a map. The saving is not asymptotic — the worst case is still Dijkstra’s — it is that far fewer nodes are settled in practice, and the settled counter on this page against Dijkstra’s on the same maze is the whole argument.
How it works
- Give the source a cost of zero, and a priority of zero plus its estimate to the target.
- Take the node with the smallest cost-plus-estimate.
- If it is the target, stop: the route is found.
- Otherwise relax each edge leaving it, exactly as Dijkstra does.
- A neighbour that gets a cheaper route joins the queue with a priority of its new cost plus its own estimate.
- Repeat until the target is taken, or the queue empties and there is no route.
Worth noticing
- The estimate must never overestimate, or the answer is wrong rather than slow. Manhattan distance on a unit-cost grid never does — there are no diagonal moves and no edge costs less than one — which is exactly why this page accepts grids only. On an arbitrary weighted graph with coordinates, straight-line distance can overestimate the moment a cheap edge joins two distant nodes, and this tool refuses rather than returning a path that is not shortest and calling it one.
- Race this against Dijkstra on the same maze. Both find a path of the same length; the difference is entirely in how much of the grid each of them had to settle.
- On an open grid the search is a narrow corridor towards the target. Raise the wall density and it spreads out, because the estimate is a worse guide when walls make the true route long.
Cost
- Best
- O(E)
- Average
- O(E)
- Worst
- O(E + V log V)
- Extra space
- O(V)
- Runs on
- a grid with walls
- Largest grid
- 11 by 7 cells
- Largest graph
- 14 nodes, 28 edges
The limits are pedagogical rather than technical: this tool keeps a cost and a predecessor for every node in every recorded step, so the size of the graph sets the size of the trace directly, and a run has to stay short enough to sit and watch. A graph that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the number of nodes and edges rather than by running it and finding out.
Graphs are generated from a seed, so the link in your address bar draws exactly the graph on your screen — no part of it is random in a way a reload could change.