What Is the A* Algorithm? How It Works, Heuristics, and Applications

Key takeaways

• The A* algorithm is used to identify the shortest possible path between two points within a graph.

• By systematically calculating the distance between points, starting from the closest pairs to the farthest possibilities, and implementing a cost function to measure the distance to the goal, the A* algorithm can calculate the most efficient route.

• The A* algorithm is different from Dijkstra’s algorithm, which is another pathfinding algorithm, since A* uses a heuristic function to quickly find the ideal path to the goal. 

The core formula of the A* algorithm is f(n) = g(n) + h(n), where the sum of the heuristic estimated cost and the cost to get from the start node to the current node equals the actual cost. Discover the underlying principle of the A* algorithm, and learn its benefits and some of the challenges of implementing it.

If you’re ready to build in-demand technical skills, earn an IBM AI Developer Professional Certificate, which gives you the opportunity to develop job-ready skills in areas such as large language modeling, AI deployment, computer vision, prompting, and more.

What is the A* algorithm?

The A* algorithm is a type of path search and graph traversal algorithm designed to identify the most efficient path between a pair of points. The Defense Advanced Research Projects Agency (DARPA) developed the A* algorithm in 1966 for use in their Shakey project, the world’s first mobile robot capable of using artificial intelligence (AI) for navigation between rooms. The A* algorithm’s relevance in computer science has grown significantly since then, with this computational method making an impact in several applications, such as computer networks, game development, and robotics.

What is the core A* formula?

The formula for the A* algorithm is f(n) = g(n) + h(n), where n represents the next node on the path, f(n) represents the actual cost, g(n) represents the cost to get from the start node to the current node, and h(n) represents the heuristic estimated cost.

How does the A* algorithm work?

The A* algorithm searches a graph by evaluating nodes from closest to farthest, selecting the path with the lowest combined actual and estimated cost at each step.

As the algorithm calculates each node, it also calculates a cost function based on the sum of the cost of the distance from the starting node to the current node, in addition to an estimated cost to reach the goal from the current node, which is measured using a heuristic function. 

What heuristic functions does the A* algorithm use?

The heuristic function in the A* algorithm plays a fundamental role in the algorithm’s effectiveness, as it identifies the cost of reaching the goal from each node, beginning with those with the shortest possible path. An optimal heuristic function shows two characteristics: consistency and admissibility. While consistency requires that the distance between any two nodes is greater than or equal to the difference in their heuristics, admissibility ensures the function doesn’t overestimate the cost.

However, multiple heuristic functions are available. The right function depends on the movement possibilities in your graph: horizontal, vertical, or diagonal. These types of heuristic functions include:

• Euclidean distance: The Euclidean distance describes the distance between two points in a straight line, at any angle, working vertically, horizontally, or diagonally, making it the shortest possible distance.

• Manhattan distance: The Manhattan distance relies on vertical and horizontal lines to find the shortest path along a grid structure. It is particularly useful in instances that do not permit diagonal movement.

• Diagonal distance: Grid-based maps with the ability to use diagonal movement can use the diagonal distance heuristic function, enabling a shorter path than the Manhattan distance.

How does the A* algorithm differ from Dijkstra's and Greedy Best-First Search?

Dijkstra’s algorithm and the Greedy Best-First Search (GBFS) algorithm, two alternative path-finding algorithms, share similarities with the A* algorithm. A* replicates Dijkstra’s ability to find the absolute shortest possible path between points, as well as GBFS’s use of heuristic functions to operate at high speed and quickly identify the path toward the goal. Although GBFS isn’t as accurate in finding the shortest path as Dijkstra’s algorithm and Dijkstra’s isn’t as fast as GBFS, A* uses the unique strengths of both to achieve a more balanced approach to finding the shortest distance between two points.

Common A* algorithm challenges

Although the A* algorithm has proven valuable in many applications, it has challenges, such as

• High memory and computational cost: limits use in storage-intensive tasks.

• Poor performance in dynamic environments: real-time graph changes cause recurring recalculations.

What are A* algorithm real-world applications?

A* algorithms have a wide range of real-world applications in computer science and artificial intelligence. Examples include:

• Game development: The A* algorithm helps video game characters find the most efficient path between points, which helps manage memory consumption and enables interaction with the surrounding environment.

• Navigation systems: Applications such as Google Maps utilize the A* algorithm when identifying the optimal route for vehicles, considering several different factors like the shortest possible path, road conditions, and the expected traffic patterns.

• Computer networking: When data flows through a network, it can take a variety of paths, but the A* algorithm can get data moving efficiently. This helps maximize performance in computer networks by reducing delays as data packets travel from one node to another.

• Artificial intelligence: AI applications, such as self-driving vehicles, use the A* algorithm for route planning and decision-making. Researchers are also experimenting with using neural networks and machine learning techniques alongside the A* algorithm for enhanced heuristic capabilities.

• Robotics: The A* algorithm helps robotics navigate environments by selecting the most efficient path to optimize energy usage while avoiding obstacles. It’s even effective in complex environments where they face uncertainty, such as airports and warehouses.

Read more: Algorithmic Design: How Algorithms Are Created and Analyzed

Explore our free AI resources

Subscribe to our weekly LinkedIn newsletter, Career Chat, for skill-building tips and updates on popular tools and certifications. Then check out some of our other free resources to keep learning about AI:

• Watch on YouTube: AI Is Changing Work—These Skills Keep You Relevant 

• Take the quiz: Which AI Course Should You Take? Find Out in 1 Minute

• Gain expert insights: 6 Questions With a Google AI Research Director

Whether you want to develop a new skill, get comfortable with an in-demand technology, or advance your abilities, keep growing with a Coursera Plus subscription. You’ll get access to over 10,000 flexible courses. 

Build job-ready skills with Coursera Plus

Start 7-day free trial

• 
• 
• 
• 

Start 7-day free trial