Short Path Algorithm Practice

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