What is A* Algorithm? Heuristic Search Explained

What is the A* Algorithm?

The A* algorithm (often referred to as "A star") is a search algorithm that finds the two points in a network, usually called a graph, that are connected by the least-cost path. It assesses potential connections among nodes by assigning each node a score based on specific criteria, then selecting routes in an orderly manner.

As a type of heuristic search algorithm, A* uses a combination of information about the path taken so far and an estimate of the remaining cost to reach the target. It is a well-known method for solving path-finding and graph-traversal problems in programming and algorithm design.

Dijkstra’s Algorithm: An Overview

Dijkstra’s Algorithm is a shortest-path algorithm used to find the minimum-cost path from a source node to all other nodes in a weighted graph, provided all edge weights are non-negative. It is widely used in routing, network design, map navigation, and graph-based optimization problems.

The algorithm works by maintaining a set of nodes whose shortest paths to the source are already known. At each step, it selects the node with the smallest tentative distance, marks it as finalized, and updates the tentative distances of its neighbors if a shorter path is found via the current node.

Greedy Best-First Search Algorithm: An Overview

Greedy Best-First Search is an informed search algorithm that selects the next node to explore based on the one that appears closest to the goal according to a heuristic function. Instead of considering the total path cost travelled so far, it focuses only on the estimated cost from the current node to the goal.

The main idea behind this algorithm is to move in the direction that looks the most promising at the moment. It is called greedy because it makes the locally best choice at each step, hoping that this will lead quickly to the goal.

A* Formula

In the A* algorithm, the formula f(n) = g(n) + h(n) is used to decide which node should be explored next.

• g(n) is the actual cost from the start node to the current node n
• h(n) is the estimated cost from the current node n to the goal node
• f(n) is the total estimated cost of the path through node n

So, A* combines:

• the distance already travelled
• the estimated distance still left

This helps the algorithm choose the path that looks most promising. A node with a smaller f(n) value is given higher priority because it is expected to lead to the goal with a lower total cost.

Want to Get Paid The Big Bucks? Join AI & MLProfessional Certificate Program in AI and MLExplore Program

Key Concepts in A* Search

By now, you have seen what the A* search algorithm is, how it works, and how the problem space is represented as a graph. Let’s now look at the key concepts that A* relies on to choose the best path efficiently.

Path Cost g(n)

The path cost g(n) is the actual cost already spent to reach the current node from the start. This is a real value, not an estimate, and it increases as the path becomes longer. Every time the algorithm moves to a new node, it adds the edge cost to the total.

For a path from the start node n0​ to the current node nk, g(n) is calculated as:

g(nk)=i=0k-1(ni,ni+1)

Here (ni,ni+1) is the cost of moving from one node to the next. This value can represent distance, time, or any other metric defined for the environment.

Heuristic Function h(n)

The heuristic h(n) estimates the cost required to reach the goal from the current node. It serves as a guide to help A* focus on the most promising direction. The key requirement for a heuristic is that it must never overestimate the true remaining cost.

This condition is expressed as:

h(n)≤h*(n)

Where h*(n) is the actual minimum cost from node n to the goal.

Common heuristic examples in grid-based pathfinding include:

Manhattan distance

h(n)=|x1-x2|+|y1-y2|

Euclidean distance

h(n)=(x1-x2)2+(y1-y2)2

Total Cost f(n)

The total cost f(n) is the combined value that A* uses to rank nodes. It adds the known path cost g(n) and the estimated remaining cost h(n). This combined score helps the algorithm decide which node looks best to explore next.

f(n)=g(n)+h(n)

Nodes with lower f(n) are considered more promising because they balance the cost already spent and the estimated cost to finish.

Open List and Closed List

A* keeps track of nodes using two lists:

Open List

• Holds nodes that have been discovered but not fully processed
• Sorted by f(n) so the lowest value is always chosen next
• New neighbors are added here

Closed List

• Holds nodes that are already evaluated
• Prevents rechecking the same nodes
• Helps in building the final path once the goal is reached

The algorithm repeats this process until it reaches the goal node or determines that no path exists.

How Does the A* Algorithm Work?

Now that you know what the A* algorithm is, let us go through its working process and the main steps:

1. Initialization of Open and Closed Sets

The algorithm starts by adding the starting node to the open set, which contains nodes that have not yet been evaluated. The closed set is initially empty and will store nodes that have already been processed.

2. Setting g(n), h(n), and f(n) Values

Each node maintains three values: g(n), h(n), and f(n)

For the initial node, g is set to 0, whereas the heuristic estimate determines its f-value.

3. Choosing the Node with the Lowest f(n)

From the open set, the node with the smallest f(n) is chosen for expansion. This is the node that appears most promising based on both the cost so far and the estimated remaining cost.

4. Transferring the Node to the Closed Set

Once a node is selected, it is moved from the open set to the closed set, meaning it will not be evaluated again.

5. Analyzing Neighboring Nodes

All neighboring nodes of the current node are checked. For each neighbor:

• If the neighbor is already in the closed set, it is skipped
• If the neighbor is not in the open set, it is added to the open set
• The g value is updated if the new path is cheaper than the previous path

6. Updating Cost Values for Neighbors

For each neighbor added or updated, the algorithm calculates:

• g(neighbor) = g(current) + cost(current, neighbor)
• h(neighbor) = heuristic estimate to the goal
• f(neighbor) = g(neighbor) + h(neighbor)

If the new g value is lower than the previous one, the neighbor’s parent pointer is updated to the current node.

7. Continuing the Search Until the Goal is Found

The algorithm continues selecting nodes from the open set and assessing their neighbors until the goal node is added to the closed set.

8. Reconstructing the Path from Goal to Start

When the goal node is reached, the path is traced by following parent pointers backwards from the goal node to the start node. This gives the final path.

Graph Representation

In A*, the problem space is represented as a graph, where each node stores information such as its position, parent node, and cost. Edges connect nodes and hold a weight that defines the movement cost, which can vary depending on terrain or restrictions.

To better understand this structure, take a look at the graph below:

A* Search Algorithm Pseudocode

In addition to understanding the key concepts, it is helpful to see how A* is implemented in a program. The pseudocode below presents the complete logic in a clear, organized way, from setting up the node lists to constructing the final route.

Pseudocode

1. OPEN = {start}, CLOSED = {}
2. g(start) = 0
3. f(start) = g(start) + h(start)
4. While OPEN is not empty:
   a. Select node n in OPEN with lowest f(n)
   b. If n = goal, return path
   c. Remove n from OPEN and add to CLOSED
   d. For each neighbor m of n:
      i. If m is in CLOSED, continue
      ii. temp = g(n) + cost(n, m)
      iii. If m not in OPEN or temp < g(m):
           parent(m) = n
           g(m) = temp
           f(m) = g(m) + h(m)
           If m not in OPEN, add m to OPEN
5. Return failure

This pseudocode shows how A* finds the shortest path from a start node to a goal node. It keeps two lists:

• OPEN: nodes that are discovered but not yet fully checked
• CLOSED: nodes that have already been checked

The algorithm begins by putting the start node in the OPEN list. For each node, it calculates: g(n), h(n), and f(n)

At each step, A* selects the node with the lowest f(n) from OPEN because it appears to be the most promising. If that node is the goal, the algorithm stops and returns the path. Otherwise, it moves that node to CLOSED and checks all its neighbors.

For every neighbor, it calculates a new path cost. If this new path is better than the old one, the algorithm updates the neighbor’s parent and cost values. This process continues until the goal is found or no path exists.

A* is efficient because it uses both the actual path cost and a heuristic estimate, which helps it reach the goal faster than uninformed search methods.

A* Algorithm: 2 Practical Examples With Code

Now that you have seen the A* algorithm in pseudocode, the next step is to understand how it works in practice. Below are two practical A* algorithm examples:

Example 1: Finding a Path in a Weighted Graph

In this example, we use A* to find the shortest path between nodes in a weighted graph. Think of it like finding the best route between cities, where each road has a different travel cost.

import heapq
def a_star(graph, start, goal, heuristic):
    open_set = [(heuristic(start, goal), start)]
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    closed_set = set()
    while open_set:
        _, current = heapq.heappop(open_set)
if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
            path.append(start)
            path.reverse()
            return path
if current in closed_set:
continue
        closed_set.add(current)
        for neighbor, cost in graph[current]:
tentative_g = g_score[current] + cost
if tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score, neighbor))
return None
# Example graph
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}
# Heuristic function
def heuristic(node, goal):
return 0
# Run A*
path = a_star(graph, 'A', 'D', heuristic)
if path:
    print("Path:", path)
else:
    print("No path found")

Output:

Path: ['A', 'B', 'C', 'D']

This code uses A* to find the shortest path by choosing the node with the lowest estimated total cost f(n) = g(n) + h(n).

Example 2: Route Planning with Custom Heuristic

This example shows A* being used with a custom heuristic function, making the algorithm more flexible for specific needs, such as terrain cost, penalties, or preferred routes.

from heapq import heappush, heappop
def custom_heuristic(a, b):
    dx = abs(a[0] - b[0])
    dy = abs(a[1] - b[1])
    return dx + dy + (dx * dy * 0.1)
def a_star_custom(start, goal, neighbors_func):
    open_set = []
    heappush(open_set, (0, start))
    came_from = {}
    g_score = {start: 0}
    while open_set:
    _, current = heappop(open_set)
if current == goal:
break
for neighbor, cost in neighbors_func(current):
new_cost = g_score[current] + cost
if neighbor not in g_score or new_cost < g_score[neighbor]:
                g_score[neighbor] = new_cost
                priority = new_cost + custom_heuristic(neighbor, goal)
                heappush(open_set, (priority, neighbor))
                came_from[neighbor] = current
path = []
while current in came_from:
        path.append(current)
        current = came_from[current]
    path.append(start)
    path.reverse()
    print("Custom path:", path)
# Example: 5x5 grid with obstacles
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
]
def neighbors_func(node):
    x, y = node
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]   # 4-directional movement
    result = []
    for dx, dy in moves:
nx, ny = x + dx, y + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == 0:
result.append(((nx, ny), 1))   # cost = 1
    return result
start = (0, 0)
goal = (4, 4)
a_star_custom(start, goal, neighbors_func)

Output:

Custom path: [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)]

A* finds the shortest path by combining the actual path cost and a heuristic estimate to reach the goal efficiently.

Become an AI and Machine Learning ExpertWith the Professional Certificate in AI and MLExplore Program

Implementation of A* Algorithm

So far, we have seen the A* algorithm in AI with examples. Here is how you can implement it in Python and Java.

Python

In Python, you can implement A* using a priority queue (heapq). Here is a simple version:

import heapq
def heuristic(node, goal):
    # Manhattan distance
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])
def a_star(grid, start, goal):
    rows = len(grid)
    cols = len(grid[0])
    priority_queue = []
    heapq.heappush(priority_queue, (0, start))
    parent = {}
    cost_so_far = {start: 0}
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    while priority_queue:
        _, current = heapq.heappop(priority_queue)
        if current == goal:
            break
        for dx, dy in directions:
            next_node = (current[0] + dx, current[1] + dy)
            if 0 <= next_node[0] < rows and 0 <= next_node[1] < cols:
                if grid[next_node[0]][next_node[1]] == 0:
                    new_cost = cost_so_far[current] + 1
                    if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
                        cost_so_far[next_node] = new_cost
                        priority = new_cost + heuristic(next_node, goal)
                        heapq.heappush(priority_queue, (priority, next_node))
                        parent[next_node] = current
    if goal not in parent and goal != start:
        return None
    path = []
    node = goal
    while node != start:
        path.append(node)
        node = parent[node]
    path.append(start)
    path.reverse()
    return path
# Example grid
# 0 = free cell, 1 = blocked cell
grid = [
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
start = (0, 0)
goal = (4, 4)
result = a_star(grid, start, goal)
if result:
    print("Shortest Path:", result)
else:
    print("No path found")

Output:

Shortest Path: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]

This program implements the A* search algorithm on a grid. It finds the shortest path from the start node to the goal node while avoiding blocked cells.

Java

In Java, A* can be implemented using a PriorityQueue. Here is how it works:

import java.util.*;
class Edge {
    String target;
    int cost;
    Edge(String target, int cost) {
        this.target = target;
        this.cost = cost;
    }
}
class GraphNode implements Comparable<GraphNode> {
    String name;
    int g;
    int h;
    int f;
    GraphNode parent;
    GraphNode(String name, int g, int h, GraphNode parent) {
        this.name = name;
        this.g = g;
        this.h = h;
        this.f = g + h;
        this.parent = parent;
    }
    @Override
    public int compareTo(GraphNode other) {
        return this.f - other.f;
    }
}
public class AStarGraph {
    static Map<String, List<Edge>> graph = new HashMap<>();
    public static int heuristic(String node, String goal) {
        Map<String, Integer> hValues = new HashMap<>();
        hValues.put("A", 7);
        hValues.put("B", 6);
        hValues.put("C", 2);
        hValues.put("D", 1);
        hValues.put("E", 0);
        return hValues.get(node);
    }
    public static void aStar(String start, String goal) {
        PriorityQueue<GraphNode> openSet = new PriorityQueue<>();
        Map<String, Integer> gScore = new HashMap<>();
        Set<String> closedSet = new HashSet<>();
        for (String node : graph.keySet()) {
            gScore.put(node, Integer.MAX_VALUE);
        }
        GraphNode startNode = new GraphNode(start, 0, heuristic(start, goal), null);
        openSet.add(startNode);
        gScore.put(start, 0);
        while (!openSet.isEmpty()) {
            GraphNode current = openSet.poll();
            if (current.name.equals(goal)) {
                printPath(current);
                return;
            }
            if (closedSet.contains(current.name)) {
                continue;
            }
            closedSet.add(current.name);
            for (Edge edge : graph.get(current.name)) {
                if (closedSet.contains(edge.target)) {
                    continue;
                }
                int newG = current.g + edge.cost;
                if (newG < gScore.get(edge.target)) {
                    gScore.put(edge.target, newG);
                    GraphNode neighbor = new GraphNode(
                        edge.target,
                        newG,
                        heuristic(edge.target, goal),
                        current
                    );
                    openSet.add(neighbor);
                }
            }
        }
        System.out.println("No path found");
    }
    public static void printPath(GraphNode goalNode) {
        List<String> path = new ArrayList<>();
        GraphNode current = goalNode;
        while (current != null) {
            path.add(current.name);
            current = current.parent;
        }
        Collections.reverse(path);
        System.out.println("Shortest Path: " + path);
    }
    public static void main(String[] args) {
        graph.put("A", Arrays.asList(new Edge("B", 1), new Edge("C", 4)));
        graph.put("B", Arrays.asList(new Edge("A", 1), new Edge("C", 2), new Edge("D", 5)));
        graph.put("C", Arrays.asList(new Edge("A", 4), new Edge("B", 2), new Edge("D", 1), new Edge("E", 7)));
        graph.put("D", Arrays.asList(new Edge("B", 5), new Edge("C", 1), new Edge("E", 3)));
        graph.put("E", Arrays.asList(new Edge("C", 7), new Edge("D", 3)));
        aStar("A", "E");
    }
}

Output:

Shortest Path: [A, B, C, D, E]

This Java program implements the A* Search Algorithm on a graph. Each node is connected to its neighbors at a cost.

As automation and AI adoption continue to rise, AI engineers will remain indispensable, making it one of the most future-proof professions in tech. Learn AI Engineering to secure your tomorrow! 🎯

Advantages and Disadvantages of A* Search Algorithm

A* is one of the most popular algorithms for pathfinding, and for good reason, as it has many advantages:

• Optimal and Complete Search

A* is guaranteed to find the shortest path, given a suitable heuristic. Unlike greedy algorithms, it doesn't rush to a solution, so the optimality is always ensured.

• Efficient Node Exploration

A* knows where it has already been and where it might go. This way, it avoids going through paths that are obviously not worth it.

• Heuristic Flexibility

The best feature of A* is that it allows the user to select their own heuristic. Manhattan distance is often effective for grids, whereas custom cost functions are usually required for terrain-based maps.

It is necessary to weigh the shortcomings of A* before adopting it for large or complicated situations: 

• High Memory Usage

A* utilizes open and closed lists to keep all the generated nodes in memory. This can lead to an enormous memory usage for very large graphs or high-resolution grids.

• Heuristic Dependency

The performance of A* heavily depends on the quality of the heuristic. A weak heuristic makes the algorithm behave like Dijkstra and slows down the search, while an overly aggressive heuristic can break optimality if not carefully designed.

• Scalability Challenges

As the problem size increases, the number of nodes to explore may grow rapidly, even with a good heuristic.

Advance Your Career With Top AI Engineering SkillsStart Learning With the Best-in-class AI ProgramExplore Program

Common Challenges and Optimization Techniques

Apart from the advantages and disadvantages, there are several practical challenges you may face while applying A* in real systems:

• Choosing the Right Heuristic Scale

A mathematically valid heuristic that is poorly scaled can still lead to inefficient searches. Normalizing heuristic values or adjusting them to match the typical edge costs in the graph often results in smoother priority ordering and fewer unnecessary node evaluations.

• Optimizing for Large Maps

On large maps, standard A* can become slow even with a good heuristic. Techniques such as hierarchical A*, which divide the map into regions and search at multiple levels, significantly reduce computational cost while preserving path quality.

• Dynamic Environments and Replanning

In environments where obstacles or costs change during execution, rerunning A* from scratch is inefficient. Incremental variants, such as reusing partial paths or applying replanning strategies, help update routes quickly without restarting the entire search.

• Balancing Accuracy and Speed

In time-critical applications, exact optimal paths may not always be necessary. Introducing bounded or weighted heuristics allows faster results by slightly relaxing optimality, which is often acceptable in games, simulations, or real-time navigation systems.

You can also watch this video for a deeper understanding of A* Algorithm, its basics concepts and how it works. Watch now!

Key Takeaways

• A* finds the shortest path efficiently by combining actual cost so far with an estimated cost to the goal, making it reliable for real-world pathfinding problems
• The algorithm’s performance depends heavily on the heuristic choice, which guides the search and helps reduce unnecessary node exploration
• A* is flexible and practical, as seen through graph-based, grid-based, and custom-heuristic implementations in Python and Java
• While accurate and complete, A* requires careful optimization for large or dynamic environments due to memory usage and scalability constraints

FAQs

1. What is the A* algorithm in artificial intelligence?

The A* algorithm is a pathfinding and graph search method that finds the shortest path between two nodes by combining the actual cost and the estimated cost to the goal.

2. Why is A* called a heuristic search algorithm?

It is called a heuristic because it uses an estimated function to predict how close a node is to the goal, rather than searching unthinkingly.

3. How does the A* search algorithm work?

It repeatedly selects the node with the lowest combined cost value, explores its neighbors, updates costs, and continues until the goal is reached.

4. Where is the A* algorithm used in real life?

The A star algorithm in AI is used in GPS navigation, robotics path planning, game AI, and route optimization systems.

5. What is the time complexity of the A* algorithm?

In the worst case, the time complexity is exponential, but a good heuristic significantly reduces the number of explored nodes in practice.