# A* Search Algorithm

The A* Search algorithm (pronounced “A star”) is an alternative to the Dijkstra’s Shortest Path algorithm. It is used to find the shortest path between two nodes of a weighted graph. The A* Search algorithm performs better than the Dijkstra’s algorithm because of its use of heuristics.

Before investigating this algorithm make sure you are familiar with the terminology used when describing Graphs in Computer Science.

Let’s decompose the A* Search algorithm step by step using the example provided below. (Use the tabs below to progress step by step).

Note that, in this graph, the heuristic we will use is the straight line distance (“as the crow flies”) between a node and the end node (Z). This distance will always be the shortest distance between two points, a distance that cannot be reduced whatever path you follow to reach node Z.

GraphStep 1234567  Start by setting the starting node (A) as the current node. Check all the nodes connected to A and update their “Shortest Distance from A” and set their “previous node” to “A”.
Update their total distance by adding the shortest distance from A and the heuristic distance to Z. Set the current node (A) to “visited” and use the unvisited node with the smallest total distance as the current node (e.g. in this case: Node C).
Check all unvisited nodes connected to the current node and add the distance from A to C to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

C -> D: 3 + 7 = 10 < ∞ – Change Node D
C -> E: 3 + 10 = 13 < ∞ – Change Node E

The next current node (unvisited node with the shortest total distance) could be either node B or node D. Let’s use node B. Check all unvisited nodes connected to the current node (B) and add the distance from A to B to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

B -> E: 4 + 12 = 16 > 13 – Do not change Node E
B -> F: 4 + 5 = 9 < ∞ – Change Node F

The next current node (unvisited node with the shortest total distance) is D. Check all unvisited nodes connected to the current node (D) and add the distance from A to D to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

D -> E: 10 + 2 = 12 < 13 – Change Node E

The next current node (unvisited node with the shortest total distance) is E. Check all unvisited nodes connected to the current node (E) and add the distance from A to E to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

E -> Z: 12 + 5 = 17 < ∞ – Change Node Z We found a path from A to Z, but is it the shortest one?

Check all unvisited nodes. In this example, there is only one unvisited node (F). However its total distance (20) is already greater than the distance we have from A to Z (17) so there is no need to visit node F as it will not lead to a shorter path.

We found the shortest path from A to Z.
Read the path from Z to A using the previous node column:
Z > E > D > C > A
So the Shortest Path is:
A – C – D – E – Z with a length of 17

Graph #1Graph #2
Apply the steps of the A* Search algorithm to find the shortest path from A to Z using the following graph: Node Status Shortest Distance from A Heurisitic Distance to Z Total Distance Previous Node A CurrentVisited 21 ABCDEF B CurrentVisited 14 ABCDEF C CurrentVisited 18 ABCDEF D CurrentVisited 18 ABCDEF E CurrentVisited 5 ABCDEF F CurrentVisited 8 ABCDEF Z CurrentVisited 0 ABCDEF

Shortest Path?

Length?

Apply the steps of the A* Search algorithm to find the shortest path from A to Z using the following graph: Node Status Shortest Distance from A Heurisitic Distance to Z Total Distance Previous Node A CurrentVisited 11 ABCDE B CurrentVisited 8 ABCDE C CurrentVisited 8 ABCDE D CurrentVisited 4 ABCDE E CurrentVisited 2 ABCDE Z CurrentVisited 0 ABCDE

Shortest Path?

Length? #### Solution...

The solution for this challenge is available to full members!
Find out how to become a member:

Did you like this challenge?

Click on a star to rate it!

Average rating 3.8 / 5. Vote count: 24

No votes so far! Be the first to rate this post.

As you found this challenge interesting...