Skip to content

A* heuristic search

A* is Dijkstra ordered by f(state) = g(state) + h(state): known path cost plus a lower bound on remaining cost. It helps when the target is specific and the heuristic focuses exploration.

Correctness contract

  • h(state) ≥ 0.
  • h(goal) = 0.
  • Admissible: h never overestimates the true remaining cost.
  • Prefer consistent: h(u) ≤ cost(u,v) + h(v) for every edge. Then a state need not be reopened after its best priority is finalized under the usual implementation.
flowchart TD
  accTitle: A-star state expansion flow
  accDescr: Pop the state with smallest known cost plus heuristic. Ignore a stale entry, finish at the goal, otherwise relax neighbors and push each improved cost with its admissible estimate.
  A["pop minimum f = g + h"] --> B{"Is heap entry current?"}
  B -->|no| A
  B -->|yes| C{"Is this the goal?"}
  C -->|yes| D["return g"]
  C -->|no| E["relax passable neighbors"]
  E --> F["push improved g + h"]
  F --> A

For four-direction unit-cost movement, Manhattan distance is admissible because each move changes row or column by only one.

Tested grid template

def a_star_grid(
    grid: Sequence[Sequence[int]], start: tuple[int, int], goal: tuple[int, int]
) -> int:
    """Return a shortest four-direction path length through zero cells."""
    if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
        raise ValueError("grid must be nonempty and rectangular")
    rows, columns = len(grid), len(grid[0])
    for row, column in (start, goal):
        if not 0 <= row < rows or not 0 <= column < columns:
            raise ValueError("endpoint outside grid")
        if grid[row][column] != 0:
            return -1

    best = {start: 0}
    frontier = [(abs(start[0] - goal[0]) + abs(start[1] - goal[1]), 0, start)]
    while frontier:
        _estimate, distance, cell = heappop(frontier)
        if distance != best[cell]:
            continue
        if cell == goal:
            return distance
        row, column = cell
        for row_step, column_step in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            neighbor = (row + row_step, column + column_step)
            if not (0 <= neighbor[0] < rows and 0 <= neighbor[1] < columns):
                continue
            if grid[neighbor[0]][neighbor[1]] != 0:
                continue
            candidate = distance + 1
            if candidate < best.get(neighbor, inf):
                best[neighbor] = candidate
                # Manhattan distance is admissible for four-direction unit moves.
                heuristic = abs(neighbor[0] - goal[0]) + abs(neighbor[1] - goal[1])
                heappush(frontier, (candidate + heuristic, candidate, neighbor))
    return -1

inline int a_star_grid(const std::vector<std::vector<int>>& grid,
                       std::pair<int, int> start,
                       std::pair<int, int> goal) {
  if (grid.empty() || grid.front().empty()) {
    throw std::invalid_argument("grid must be nonempty and rectangular");
  }
  const int rows = static_cast<int>(grid.size());
  const int columns = static_cast<int>(grid.front().size());
  for (const auto& row : grid) {
    if (static_cast<int>(row.size()) != columns) {
      throw std::invalid_argument("grid must be nonempty and rectangular");
    }
  }
  const auto valid_cell = [&](const std::pair<int, int>& cell) {
    return cell.first >= 0 && cell.first < rows && cell.second >= 0 &&
           cell.second < columns;
  };
  if (!valid_cell(start) || !valid_cell(goal)) {
    throw std::invalid_argument("endpoint outside grid");
  }
  if (grid[start.first][start.second] != 0 ||
      grid[goal.first][goal.second] != 0) {
    return -1;
  }

  typedef std::tuple<int, int, int, int> State;
  std::priority_queue<State, std::vector<State>, std::greater<State>> frontier;
  std::vector<std::vector<int>> best(
      rows, std::vector<int>(columns, std::numeric_limits<int>::max()));
  best[start.first][start.second] = 0;
  frontier.push(State(std::abs(start.first - goal.first) +
                          std::abs(start.second - goal.second),
                      0, start.first, start.second));
  const int moves[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  while (!frontier.empty()) {
    const State state = frontier.top();
    frontier.pop();
    const int distance = std::get<1>(state);
    const int row = std::get<2>(state);
    const int column = std::get<3>(state);
    if (distance != best[row][column]) {
      continue;
    }
    if (row == goal.first && column == goal.second) {
      return distance;
    }
    for (int move = 0; move < 4; ++move) {
      const int next_row = row + moves[move][0];
      const int next_column = column + moves[move][1];
      if (next_row < 0 || next_row >= rows || next_column < 0 ||
          next_column >= columns || grid[next_row][next_column] != 0) {
        continue;
      }
      const int candidate = distance + 1;
      if (candidate < best[next_row][next_column]) {
        best[next_row][next_column] = candidate;
        // Manhattan distance is admissible for four-direction unit moves.
        const int heuristic = std::abs(next_row - goal.first) +
                              std::abs(next_column - goal.second);
        frontier.push(
            State(candidate + heuristic, candidate, next_row, next_column));
      }
    }
  }
  return -1;
}

inline int a_star_grid(const std::vector<std::vector<int>>& grid,
                       std::pair<int, int> start,
                       std::pair<int, int> goal) {
  if (grid.empty() || grid.front().empty()) {
    throw std::invalid_argument("grid must be nonempty and rectangular");
  }
  const int rows = static_cast<int>(grid.size());
  const int columns = static_cast<int>(grid.front().size());
  for (const auto& row : grid) {
    if (static_cast<int>(row.size()) != columns) {
      throw std::invalid_argument("grid must be nonempty and rectangular");
    }
  }
  const auto valid_cell = [&](const std::pair<int, int>& cell) {
    return cell.first >= 0 && cell.first < rows && cell.second >= 0 &&
           cell.second < columns;
  };
  if (!valid_cell(start) || !valid_cell(goal)) {
    throw std::invalid_argument("endpoint outside grid");
  }
  if (grid[start.first][start.second] != 0 ||
      grid[goal.first][goal.second] != 0) {
    return -1;
  }

  typedef std::tuple<int, int, int, int> State;
  std::priority_queue<State, std::vector<State>, std::greater<State>> frontier;
  std::vector<std::vector<int>> best(
      rows, std::vector<int>(columns, std::numeric_limits<int>::max()));
  best[start.first][start.second] = 0;
  frontier.push(State(std::abs(start.first - goal.first) +
                          std::abs(start.second - goal.second),
                      0, start.first, start.second));
  const int moves[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  while (!frontier.empty()) {
    const State state = frontier.top();
    frontier.pop();
    const int distance = std::get<1>(state);
    const int row = std::get<2>(state);
    const int column = std::get<3>(state);
    if (distance != best[row][column]) {
      continue;
    }
    if (row == goal.first && column == goal.second) {
      return distance;
    }
    for (int move = 0; move < 4; ++move) {
      const int next_row = row + moves[move][0];
      const int next_column = column + moves[move][1];
      if (next_row < 0 || next_row >= rows || next_column < 0 ||
          next_column >= columns || grid[next_row][next_column] != 0) {
        continue;
      }
      const int candidate = distance + 1;
      if (candidate < best[next_row][next_column]) {
        best[next_row][next_column] = candidate;
        // Manhattan distance is admissible for four-direction unit moves.
        const int heuristic = std::abs(next_row - goal.first) +
                              std::abs(next_column - goal.second);
        frontier.push(
            State(candidate + heuristic, candidate, next_row, next_column));
      }
    }
  }
  return -1;
}

Choose A*, Dijkstra, or BFS

Situation Choice
Unit edges, no useful heuristic BFS
Nonnegative edges, many targets/all distances Dijkstra
One target, nonnegative edges, strong lower bound A*
Negative edge Bellman–Ford or another suitable model

Worst-case work remains comparable to Dijkstra when the heuristic gives no guidance. An overestimating heuristic may be faster but can lose optimality.

Practice