A* Search Algorithm

6 min readSep 12, 2022

A* search algorithm is a path finding algorithm that finds the single-pair shortest path between the start node(source) and the target node(destination) of a weighted graph. The algorithm not only considers the actual cost from the start node to the current node(g) but also tries to estimate the cost will take from the current node to the target node using heuristics (h). Then it selects the node that has the lowest f-value(f=g+h) to be the next node to move until it hits the target node. Dijkstra’s algorithm is a special case of A* algorithm where heuristic is 0 for all nodes.

Table of Contents· How A* Algorithm Works?
· A* algorithm vs. Dijkstra’s algorithm
· Graphical Explanation
  ∘ demo iteration 1
  ∘ demo iteration 2
  ∘ demo iteration 3
  ∘ demo iteration 4
  ∘ demo iteration 5
  ∘ final result
· Code Implementation
  ∘ Data Structure
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

How A* Algorithm Works?

The formula for A* algorithm considers two functions, g(n) and h(n). Imagine that we are currently at node n, g(n) tells us the actual cost we took from the start node to the current node. h(n) is a heuristic function that estimates the cost we will take to get to the target node from the current node. Therefore, h(n) is an educated guess and it is crucial to determine the performance of A* algorithm. Based on the sum of the g(n) and h(n), f(n), the algorithm is able to estimate the total cost from the start node to the end node.

f(n) = g(n) + h(n)f(n): the estimate of the total cost from start node to target node through node n
g(n): actual cost from start node to node n
h(n): estimated cost from node n to target node

The algorithm selects the minimum f-value node as the next current node to explore and continuously update g(n) and h(n) if a better path is found for nodes it encountered. This process continues until the algorithm reaches the target node.

A* algorithm vs. Dijkstra’s algorithm

A* Algorithm only finds the shortest path between the start node and the target node, whereas Dijkstra’s algorithm finds the shortest path from the start node to all other nodes because every node in a graph is a target node for it.

A* algorithm runs faster than Dijkstra’s algorithm because it uses a heuristic to direct in the correct direction towards the target node. However, Dijkstra’s algorithm expands evenly in all of the different available directions because it has no knowledge regarding the target node before hand, it always processes the node that is the closest to the start node based on the cost or distance it already took.

Graphical Explanation

Heuristic is crucial to the performance of A* algorithm. The heuristic function we use here just for the demo purpose.

Step 1
- a: Set the distance to the start node itself to 0 and the distance to all other nodes to infinity.
- b: Calculate the f value for the start node and set the previous node to none/nil/null.
- c: Initialize an open list and close list which are empty initially.

Step 2: Place the start node into the open list

Step 3
- a: Find the node with the minimum f-value in the open list and removed from the list. Denote this node as the current node.
- b: Check if the current node is the target node or not
- c: Populate all the current node’s neighboring nodes and do following checks for each neighboring nodes

1. Is the neighboring node in the close list?
   - Yes. Skip this node.
   - No. Go to 2.2. Calculate g value for the neighboring node and check if a better  
   path(lower g value) is found?
   - No, Skip this node
   - Yes. Go to 3.3. Calculate g, h and f value for the neighboring node and set  
   the previous node to the current node4. Check if the neighbor node in the open list?
   - Yes. Update g, h and f value of the neighboring node in the  
     open list
   - No. Insert this neighboring node to the open list

- d: Place the current node to the close list because we have expanded this node.

Step 4: Repeat Step 3 until reaches the target node

demo iteration 1

demo iteration 2

demo iteration 3

demo iteration 4

demo iteration 5

final result

At the end, we can backtrack the shortest path using the previous node. In this demo, we use A* algorithm to search the shortest path without necessarily search all the graph.(We haven’t examined node 4 yet, so you can see the node 4 is till on the open list). Unlike Dijkstra’s algorithm, it has to expand all the nodes in the graph.

You can check here to know more about Dijkstra’s algorithm.

Code Implementation

Data Structure

Use Priority queue to get the lowest f-value node for each run. In this demo, we implement code using min heap data structure .

Complexity

Time: O(nlog(n)), Space: O(n)
n: the total number of nodes in the graph

Pseudocode

# initialize a min Heap contains the start node
minHeap = MinHeap([start])While minHeap is not empty:
  # grab the minimum f-value node from minHeap and denote as current
  current = minHeap.pop()  # check if current is the target node
  if current == target:
      break
   
  # populate all current node's neighbors
  for neighbor in current.neighbors:
      compute neighbor's g, h, f value
      
      if neighbor in minHeap:
         if neighbor.g < neighbor.g in minHeap:
             update minHeap
      else:
         insert neighbor into minHeap

Golang

When we use a heap data structure to select a node with the shortest distance to the start node, the close list will become redundant. Because we already found the smallest distance to reach the expanded node, it will not have a chance to add back to the min heap. (When we found a new shorter path to a node, we will add it to the min heap)

Therefore, we can remove the close list in the code. (I comment out code regarding close list in the code).

core code

min heap

Python

code code

min heap

You can access the source code here.

Other shortest path algorithms