Deep dive into A star (A*)Algorithm

6 min readDec 23, 2022

The A* algorithm is a search algorithm that is used to find the shortest path. It helps us to find a shorted path between two given points in a graph. A* is somewhat similar to Dijkstra’s algorithm in which at each node, we choose the neighbour with minimum distance to be our next exploring node, but in A* we have a additional value that is heuristic value that is assigned to each node.

Heuristic value is simply a value that is estimation for the cost of reaching the end node from a given node.

A* star has a formula to calculate the distance from current node to next node:

f(n) = g(n)+h(n)
// g(n) distance from starting node to next node
// h(n) heiuristic values(estimation value from that node to end node)

At each step , we calculate the distance cost of traveling from one node to another and for that we need to add the distance from starting node to next node with its heuristic value.

Undirected graph with weighted edges and defined heuristic value. (figure 1.0)

Here is how the A* algorithm works:

We start from the root node.
Explore the current node and catch the connecting neighbours.

// we update the weight of each node using the formula:
f(n) = g(n)+h(n)

Then we check the neighbour with minimum connecting node(using about formula) and compare with other possible path.
If a node with minimum node exist then we start exploring that node.

Let’s understand step by step how A* will work on figure 1.0 (undirected graph).

let’s suppose A is our root node and G is our target node. we need to start from A and reach G with minimum cost possible.

At A, we have S, B and E connected. Let’s calculate the cost of traveling to each of these nodes and choose the one with minimum cost.

Calculating the traveling cost from A to S

// Calculating traveling cost from A to S.
f(n) = g(n)+h(n)
// so what is the value of g(n) , i.e = 3 
// what is the h(n) , i.e = 9.
f(n) = 3 + 9
f(n) = 12.
So the cost of traverling from A to S is 12. and the path is A -> S

Calculating the traveling cost from A to B

// Calculating traveling cost from A to B.
f(n) = g(n)+h(n)
// so what is the value of g(n) , i.e = 5
// what is the h(n) , i.e = 5.
f(n) = 5 + 5
f(n) = 10.
So the cost of traverling from A to B is 10. and the Path is A -> B

Calculating the traveling cost from A to E

// Calculating traveling cost from A to E.
f(n) = g(n)+h(n)
// so what is the value of g(n) , i.e = 6
// what is the h(n) , i.e = 11.
f(n) = 6 + 11
f(n) = 17.
So the cost of traverling from A to E is 17 and the path is A -> E

As we can check, the minimum connecting edge is B with cost 10, so we travel to B. and start exploring B. we need to keep S(cost 12) and E(cost 17) on hold as we’ll compare with other values if these values are less or not.

selected B as next successor and started exploring B. also keep track of path **A -> B**

At B, we have S and D as our neighbours. Let’s calculate the cost of traveling to each of these nodes and choose the one with minimum cost.

Calculating the traveling cost from B to S

// Calculating traveling cost from B to S.
f(n) = g(n)+h(n)
// so what is the value of g(n) , i.e = 7(cost of traveling to S through B)
// what is the h(n) , i.e = 9.
f(n) = 7 + 9
f(n) = 16.
So the cost of traverling from B to S is 16 and Path is A -> B -> S

Calculating the traveling cost from B to D

// Calculating traveling cost from B to D.
f(n) = g(n)+h(n)
// so what is the value of g(n) , i.e = 6(cost of traveling to D through B)
// what is the h(n) , i.e = 4.
f(n) = 6 + 4
f(n) = 10.
So the cost of traverling from B to D is 10 and Path is A -> B -> D

As we can check, the minimum connecting edge is D with cost 10, we’ll check if 10 is greater than our previous values or not(example we have S and E on hold with values 12 and 17). In this case 10 is less than 12 and 17, so we start exploring D and put S (with cost 16) on hold along with E.

selected D as next successor and started exploring D. Also keep track of path **A -> B -> D**

At D, we have F, and E connected, as B is already processed. Let’s calculate the cost of traveling to each of these nodes and choose the one with minimum cost.

Calculating the traveling cost from D to E

// Calculating traveling cost from D to E.
f(n) = g(n)+h(n)
// so what is the value of g(n) , i.e = 13 (cost of traveling to E through D)
// what is the h(n) , i.e = 11.
f(n) = 13 + 11
f(n) = 24.
So the cost of traverling from D to E  is 24. and Path is A -> B -> D -> E

Calculating the traveling cost from D to F

// Calculating traveling cost from D to F.
f(n) = g(n)+h(n)
// so what is the value of g(n) , i.e = 8 (cost of traveling to F through D)
// what is the h(n) , i.e = 2.
f(n) = 8 + 2
f(n) = 10.
So the cost of traverling from D to F is 10 and Path is A -> B -> D -> F

As we can check, the minimum connecting edge is F with cost 10, We’ll also compare this value with with previous on hold value that is S(cost 16) and E(24), in both the cases, our new value F is less. So we select F and start exploring F.

selected F as next successor and started exploring F. Also keep track of path **A -> B -> D -> F**

At F, we have G connected. Let’s calculate the cost of traveling to G.

Calculating the traveling cost from F to G

// Calculating traveling cost from F to G.
f(n) = g(n)+h(n)
// so what is the value of g(n) , i.e = 10(cost of traveling to G through F)
// what is the h(n) , i.e = 0.
f(n) = 10 + 0
f(n) = 10.
So the cost of traverling from F to G is 10 
and the Path is A -> B -> D -> F -> G

We’ll compare this value with our previously on hold values that is S(cost 16) and E(24), in both the cases, our new value G is less. So we select G and as we have reached our target node, we stop the further execution and display the cost that is 10 and path which we have traversed to reach this end node with minimum cost that is A -> B -> D -> F -> G

selected G as next successor. Also keep track of path **A -> B -> D -> F -> G**

At each step we compare the cost with other processed paths in order to find the best one and start exploring that path.

Hope this might gives a understanding of how A* algorithm works.

If you are new here, do checkout my other blogs for few of the most famous algorithms that i have covered to make this easy.

Checkout these Algorithm blogs:

Other Life changing blogs for productivity and Focus: