Before completing this task, you will need to familiarise yourself with the following 2 algorithms used to find the shortest path between two nodes of a weighted graph:

#### Dijkstra’s Short Path Algorithm

For each of the weighted graph below, complete the table below to show the steps needed to find the shortest path between node A and node Z using the Dijkstra’s Short Path Algorithm. Note that on these graphs, the weight of each edge represents the distance in miles between two nodes.

Graph #1Graph #2Graph #3Graph #4

**Shortest Path?**

**Length?**

**Shortest Path?**

**Length?**

**Shortest Path?**

**Length?**

**Shortest Path?**

**Length?**

Node | Status | Shortest Distance from A | Previous Node |

A | |||

B | |||

C | |||

D | |||

E | |||

F | |||

G | |||

H | |||

Z |

#### A* Algorithm

On the graphs below, the heuristic values specified for each node of the graph represent the distance in a straight line (as the crow flies) between the node and the destination node (Z).

Graph #1Graph #2Graph #3Graph #4

**Shortest Path?**

**Length?**

**Shortest Path?**

**Length?**

**Shortest Path?**

**Length?**

**Shortest Path?**

**Length?**

Node | Status | Shortest Distance from A | Heurisitic Distance to Z | Total Distance | Previous Node |

A | |||||

B | |||||

C | |||||

D | |||||

E | |||||

F | |||||

G | |||||

H | |||||

Z |