A* Algorithm

Tags

A* Algorithm

Category

Famous Algorithms

Difficulty

Very Hard

Problem Statement

Given a weighted graph (or grid) with a start node and an end node, find the shortest path from start to end. A* extends Dijkstra's algorithm by incorporating a heuristic function h(n) that estimates the remaining cost from node n to the goal. This heuristic guides the search toward the goal, often exploring far fewer nodes than Dijkstra's while still guaranteeing an optimal path (when the heuristic is admissible).

Intuition

Dijkstra's algorithm explores nodes in order of their distance from the source, expanding outward uniformly in all directions. A* improves on this by prioritizing nodes that appear to be on the shortest path to the goal. It evaluates each node n using f(n) = g(n) + h(n), where g(n) is the actual cost from start to n, and h(n) is the heuristic estimate from n to the goal. If h(n) never overestimates the true remaining cost (admissibility), A* is guaranteed to find the optimal path. If h(n) is also consistent (satisfies the triangle inequality), nodes are never re-expanded.

Approach

  1. Initialize:
    • Create an open set (min-heap / priority queue) with the start node, keyed by f = g + h.
    • Set g[start] = 0 and f[start] = h(start).
    • Create a closed set (visited set), initially empty.
    • Create a parent map for path reconstruction.
  2. While the open set is non-empty:
    • Extract the node current with the smallest f value.
    • If current is the goal, reconstruct and return the path using parent.
    • Add current to the closed set.
    • For each neighbor next of current:
      • If next is in the closed set, skip.
      • Compute tentative_g = g[current] + cost(current, next).
      • If tentative_g < g[next] (or next has not been visited):
        • Set g[next] = tentative_g.
        • Set f[next] = tentative_g + h(next).
        • Set parent[next] = current.
        • Add (or update) next in the open set.
  3. If the open set is exhausted without reaching the goal, no path exists.

Pseudocode

function aStarSearch(graph, start, goal, heuristic):
    openSet = min-heap ordered by f value
    gScore = map with default value infinity
    gScore[start] = 0
    fScore = map with default value infinity
    fScore[start] = heuristic(start, goal)
    openSet.push((fScore[start], start))
    parent = empty map
    closedSet = empty set

    while openSet is not empty:
        (fCurrent, current) = openSet.pop()
        if current == goal:
            return reconstructPath(parent, current)

        closedSet.add(current)

        for (neighbor, edgeCost) in graph[current]:
            if neighbor in closedSet:
                continue
            tentative_g = gScore[current] + edgeCost
            if tentative_g < gScore[neighbor]:
                parent[neighbor] = current
                gScore[neighbor] = tentative_g
                fScore[neighbor] = tentative_g + heuristic(neighbor, goal)
                openSet.push((fScore[neighbor], neighbor))

    return null  // no path found

function reconstructPath(parent, current):
    path = [current]
    while current in parent:
        current = parent[current]
        path.prepend(current)
    return path

Time & Space Complexity

  • Time: O(E log V) in the worst case, same as Dijkstra's, where E is the number of edges and V is the number of vertices. With a perfect heuristic (h = h*), A* expands only the nodes on the shortest path. In practice, the better the heuristic, the fewer nodes are expanded.
  • Space: O(V) for the open set, closed set, and score maps. In grid-based pathfinding, this can be O(rows * cols) in the worst case.

Key Insights

  • Admissibility: The heuristic must never overestimate the true cost to the goal. If it does, A* may return a suboptimal path. Common admissible heuristics for grids: Manhattan distance (4-directional movement), Euclidean distance (any-angle movement), Chebyshev distance (8-directional movement).
  • Consistency (monotonicity): A heuristic is consistent if h(n) <= cost(n, n') + h(n') for every edge (n, n'). Consistency implies admissibility and guarantees that once a node is expanded, its g value is optimal (no need to re-expand).
  • Degenerations: If h(n) = 0 for all nodes, A* becomes Dijkstra's algorithm. If h(n) always equals the true remaining cost, A* only expands nodes on the optimal path.
  • Comparison with Dijkstra: A* is never worse than Dijkstra in terms of nodes expanded (given a consistent heuristic), but it requires computing the heuristic, which adds per-node overhead.
  • Weighted A:* Using f(n) = g(n) + w * h(n) with w > 1 trades optimality for speed. The resulting path is at most w times the optimal cost.

Edge Cases

  • Start equals goal: Return immediately with a path of length 0 and cost 0.
  • No path exists: The open set empties before the goal is reached. Return null or indicate failure.
  • All edge weights are equal (unweighted graph): A* with a good heuristic still outperforms BFS by prioritizing direction toward the goal.
  • Negative edge weights: A* (like Dijkstra's) does not support negative edge weights. Use Bellman-Ford instead.
  • Large open spaces (grids with few obstacles): A* with a good heuristic will find the path quickly, expanding nodes mostly along the direct route.
  • Maze-like environments: The heuristic provides less guidance, and A* may degenerate toward Dijkstra-like behavior, but it will still find the optimal path.
  • Heuristic is inadmissible (overestimates): A* may find a path faster but it is not guaranteed to be optimal.

Linked mentions