A* Search

Graphs

avgO((V + E) log V)worstO((V + E) log V)spaceO(V)

Start at (7, 2): g = 0 and the Manhattan estimate to the end is 24

1 / 297

Code

function aStar(grid: Grid, start: number, end: number) {  const h = (cell: number) => grid.manhattan(cell, end);  const g = new Map([[start, 0]]);  const prev = new Map<number, number>();  const closed = new Set<number>();  // Ordered by f = g + h; ties go to the smaller h (closer to the goal).  const open = new PriorityQueue<number>();  open.push(start, [h(start), h(start)]);  while (open.size > 0) {    const cell = open.pop()!;    if (closed.has(cell)) continue; // stale: a cheaper copy was already popped    closed.add(cell);    if (cell === end) return { cost: g.get(end)!, path: buildPath(prev, end) };    for (const next of grid.neighbours(cell)) {      if (grid.isWall(next) || closed.has(next)) continue;      const tentative = g.get(cell)! + grid.cost(next);      if (tentative < (g.get(next) ?? Infinity)) {        g.set(next, tentative);        prev.set(next, cell);        open.push(next, [tentative + h(next), h(next)]);      }    }  }  return { cost: Infinity, path: [] };}function buildPath(prev: Map<number, number>, end: number) {  const path = [end];  while (prev.has(path[0])) path.unshift(prev.get(path[0])!);  return path;}

procedure AStar(grid, start, end)  h(cell) ← |row − end.row| + |col − end.col|    ▷ Manhattan distance  g ← {start: 0}  prev ← empty map  closed ← ∅  ▷ priority (f, h) with f = g + h, compared in that order  open ← min-priority queue  insert start into open with priority (h(start), h(start))  while open is not empty do    cell ← extract-min(open)    if cell ∈ closed then skip it    add cell to closed    if cell = end then return g[end], buildPath(prev, end)    for each neighbour next of cell (up, right, down, left) do      if next is a wall or next ∈ closed then skip it      tentative ← g[cell] + cost(next)      if tentative < g[next] (∞ if unset) then        g[next] ← tentative        prev[next] ← cell        insert next into open with priority (tentative + h(next), h(next))      end if    end for  end while  return ∞, no pathend procedureprocedure buildPath(prev, end)  path ← [end]  while prev[first of path] exists do prepend it to path  return pathend procedure

Variables

g=0h=24f=24open=1

Counters

visited: 0
relaxations: 0

Draw

Size

Drag on the grid to draw. Grab the start or end cell to move it. Edits re-run the search from step 1.

How it works

A* is Dijkstra's algorithm steered by a heuristic: it expands the cell with the smallest f = g + h, where g is the cost so far and h is the Manhattan distance still to go. Because h never overestimates on a 4-connected grid, the first path to the end is still optimal, but far fewer cells are expanded on the way.

Complexity

Best: O(1)
Average: O((V + E) log V)
Worst: O((V + E) log V)
Space: O(V)

A* Search

How it works

Complexity

Search algorithms