A* Search Algorithm

Posted on February 1, 2018 by Administrator Posted in A Level Concepts, A Level Quiz, Algorithms, Computer Science, Computing Concepts, Solved Challenges

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