ayodhyya.comA* (A-Star) is a best-first search algorithm that finds the shortest path from a start to a goal using a heuristic function. It combines the actual cost from the start with an estimated cost to the goal: f(n) = g(n) + h(n).
When the heuristic is admissible (never overestimates the true cost), A* is guaranteed to find the optimal path and is more efficient than Dijkstra for goal-directed search.
A* Algorithm with Admissible Heuristic
A* maintains an open set (priority queue) of frontier nodes ordered by f(n). It expands the node with the smallest f value, updating g-scores of neighbors. The algorithm terminates when the goal is popped from the open set.
Common admissible heuristics include Euclidean distance, Manhattan distance, and octile distance for grid-based pathfinding.
int aStar(vector>& grid, pair start, pair goal) {
int R = grid.size(), C = grid[0].size();
auto heuristic = [&](int x, int y) { return abs(x - goal.first) + abs(y - goal.second); };
priority_queue, vector>, greater<>> pq;
vector> g(R, vector(C, INT_MAX));
pq.push({0, start.first, start.second});
g[start.first][start.second] = 0;
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
while (!pq.empty()) {
auto [f, x, y] = pq.top(); pq.pop();
if (x == goal.first && y == goal.second) return g[x][y];
if (f > g[x][y] + heuristic(x, y)) continue;
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < R && ny >= 0 && ny < C && grid[nx][ny] == 0) {
int ng = g[x][y] + 1;
if (ng < g[nx][ny]) {
g[nx][ny] = ng;
pq.push({ng + heuristic(nx, ny), nx, ny});
}
}
}
}
return -1;
} Frequently Asked Questions
What makes a heuristic admissible?
A heuristic is admissible if it never overestimates the actual cost to reach the goal. For grid pathfinding, Manhattan distance is admissible when movement is only cardinal, and Euclidean distance is always admissible.
How does A* compare to Dijkstra?
A* is Dijkstra with a heuristic. Dijkstra (h=0) explores equally in all directions. A* with a good heuristic focuses search toward the goal, drastically reducing explored nodes while preserving optimality.
Originally published on Ayodhyya. Last updated June 1, 2026.
When A* Beats Dijkstra and BFS
BFS finds the shortest path in unweighted graphs. Dijkstra handles weighted edges. A* adds a heuristic that estimates distance to the goal, letting it expand far fewer nodes. When the heuristic is admissible (never overestimates), A* is guaranteed to find the optimal path while exploring dramatically less of the graph.
The Heuristic Choice
For grid problems, Manhattan distance suits 4-directional movement and Euclidean suits 8-directional. A zero heuristic degenerates A* to Dijkstra; an overly optimistic one degenerates to greedy best-first and can miss the optimum. The heuristic must be consistent for the closed-set optimization to hold.
Complexity and Pitfalls
Time is O(E) in the worst case with a poor heuristic; space is O(V) for the open and closed sets. In practice, a good heuristic makes A* dramatically faster. Common bugs include forgetting to re-open nodes when a cheaper path arrives and using a heuristic that violates consistency.