Short Path Algorithm Practice

Posted on January 10, 2023 by Administrator Posted in A Level Concepts, A Level Quiz, Algorithms, Computer Science, Computing Concepts

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