V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

A* Search

Order frontier cells by path cost plus heuristic and reconstruct an optimal route when the goal is settled.

Core idea

A* orders its priority queue by f equals g plus h: the exact cost already paid plus a heuristic estimate to the goal. Relaxation updates a neighbor when a cheaper g value appears.

Read the visualization

Open cells form the frontier, closed cells are settled, and the active cell has the smallest f score. Once the goal settles, predecessor arrows reveal the route.

6
🚩

Initialize the start with zero path cost and its heuristic estimate to the goal.

1function astar(grid: Grid, s: Cell, t: Cell): Cell[] {
2 const open = new MinHeap<Cell>(); // init f = g + h
3 g.set(s, 0); open.push(s, h(s));
4 while (!open.empty()) {
5 const cur = open.pop(); // pop f minimum
6 if (cur === t) break; // goal point goal queue → already optimal
7 for (const nb of neighbors(cur)) { // goal direction goal
8 const ng = g.get(cur) + 1;
9 if (ng < (g.get(nb) ?? Infinity)) { // relax
10 g.set(nb, ng); parent.set(nb, cur);
11 open.push(nb, ng + h(nb)); // f = g + h trace queue
12 }
13 }
14 }
15 return tracePath(parent, t); // trace parent backtrack
16}
rulef = g + h(h = Manhattan distance)
open{ (1, 0) f=6 }
expanded0
1 / 13

Complexity and tradeoffs

Time: Worst O((V+E) log V). Space: O(V). An admissible consistent heuristic preserves optimality and often explores far fewer states than Dijkstra.

Invariant: With a consistent heuristic, every closed state's g score is optimal and f scores do not decrease along an optimal path.

Where it fits

A* powers pathfinding and planning when a useful lower-bound heuristic exists. Setting h to zero gives Dijkstra; an overestimating heuristic may trade optimality for speed.