Pattern Guide
A* Search
"Dijkstra guided by a heuristic. Finds optimal path faster when heuristic is good."
A* search finds the shortest path from start to goal by prioritizing nodes based on f(n) = g(n) + h(n), where g(n) is the actual distance from start and h(n) is an admissible heuristic (never overestimates the true remaining distance). When h(n) = 0, A* becomes Dijkstra. With a perfect heuristic, A* is O(n). Applications: robot navigation, game pathfinding, k-th shortest path, and puzzle solving.
Problems you can solve with this pattern
3 problems · click any to start solving
function aStar(grid, start, goal) {
const [rows, cols] = [grid.length, grid[0].length];
const h = (r, c) => Math.abs(r - goal[0]) + Math.abs(c - goal[1]); // Manhattan
const g = Array.from({length: rows}, () => new Array(cols).fill(Infinity));
g[start[0]][start[1]] = 0;
// Min-heap: [f, r, c]
const heap = [[h(start[0], start[1]), start[0], start[1]]];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]); // use real min-heap in production
const [f, r, c] = heap.shift();
if (r === goal[0] && c === goal[1]) return g[r][c];
if (f > g[r][c] + h(r, c)) continue; // outdated entry
for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {
const [nr, nc] = [r+dr, c+dc];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === 1) continue;
const ng = g[r][c] + 1;
if (ng < g[nr][nc]) {
g[nr][nc] = ng;
heap.push([ng + h(nr, nc), nr, nc]);
}
}
}
return -1; // unreachable
}A* uses a priority queue ordered by f = g + h. Expand the node with smallest f first. Guarantee: if h is admissible (h(n) ≤ true remaining distance), A* finds the optimal path. If h is consistent (h(n) ≤ cost(n,n') + h(n')), each node is expanded at most once — more efficient. Common heuristics: Manhattan distance (grid, 4-directional), Euclidean distance, Chebyshev distance (8-directional).
function aStar(grid, start, goal) {
const [rows, cols] = [grid.length, grid[0].length];
const h = (r, c) => Math.abs(r - goal[0]) + Math.abs(c - goal[1]); // Manhattan
const g = Array.from({length: rows}, () => new Array(cols).fill(Infinity));
g[start[0]][start[1]] = 0;
// Min-heap: [f, r, c]
const heap = [[h(start[0], start[1]), start[0], start[1]]];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]); // use real min-heap in production
const [f, r, c] = heap.shift();
if (r === goal[0] && c === goal[1]) return g[r][c];
if (f > g[r][c] + h(r, c)) continue; // outdated entry
for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {
const [nr, nc] = [r+dr, c+dc];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === 1) continue;
const ng = g[r][c] + 1;
if (ng < g[nr][nc]) {
g[nr][nc] = ng;
heap.push([ng + h(nr, nc), nr, nc]);
}
}
}
return -1; // unreachable
}Common heuristics:
- 4-directional grid: Manhattan distance |Δr| + |Δc|
- 8-directional grid: Chebyshev distance max(|Δr|, |Δc|)
- 2D Euclidean: √(Δr² + Δc²)
- Puzzle: sum of Manhattan distances for each tile
A* vs Dijkstra: Same algorithm structure, but A* uses f=g+h instead of f=g. When h=0, identical. With a good h, A* explores far fewer nodes.
Limitations: A* requires knowing the goal ahead of time. For multi-target problems or when goal is unknown, use Dijkstra.