Graph AlgosGraph Algorithms

A* Search

Point-to-point shortest path that steers Dijkstra toward the goal with a heuristic h(v): pop by f = g + h; optimal when h never overestimates.

Learn A* Search →

Grid — One row per line: "." open, "#" wall, "S" start, "T" target. Up to 10×14.

Open set (by f = g + h)

cell	g	h	f
(0,0)	0	11	11

1/54Start at (0,0), target (4,7). h = Manhattan distance to the target — it never overestimates on a 4-connected grid, so A* with this heuristic still finds an optimal path while expanding far fewer cells than plain BFS.

StartTargetWallOpen set (cell shows f)Expanding nowClosedFinal path

PseudocodeLearn A* Search →

1g[start] = 0; open = {start with f = h(start)}
2while open not empty:
3  u = cell in open with smallest f = g + h
4  if u == target: reconstruct path and stop
5  closed.add(u)
6  for v in 4-neighbors(u) not wall, not closed:
7    if g[u] + 1 < g[v]:
8      g[v] = g[u] + 1; parent[v] = u; f[v] = g[v] + h(v); open.add(v)
9open empty → no path

Variables

h11

Complexity

best O(L log L)

avg depends on heuristic

worst O((V + E) log V)

space O(V)

Speed