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 |
LMC Simulator
Flowchart Studio
Python Syntax