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.

**“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.

**“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.

E -> Z: 12 + 5 = 17 < ∞ – Change Node Z

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**

#### Your Task

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 | 21 | ||||

B | 14 | ||||

C | 18 | ||||

D | 18 | ||||

E | 5 | ||||

F | 8 | ||||

Z | 0 |

**Shortest Path?**

**Length?**