# 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 CurrentVisited ABCDEFGH B CurrentVisited ABCDEFGH C CurrentVisited ABCDEFGH D CurrentVisited ABCDEFGH E CurrentVisited ABCDEFGH F CurrentVisited ABCDEFGH G CurrentVisited ABCDEFGH H CurrentVisited ABCDEFGH Z CurrentVisited ABCDEFGH

#### 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 CurrentVisited ABCDEFGH B CurrentVisited ABCDEFGH C CurrentVisited ABCDEFGH D CurrentVisited ABCDEFGH E CurrentVisited ABCDEFGH F CurrentVisited ABCDEFGH G CurrentVisited ABCDEFGH H CurrentVisited ABCDEFGH Z CurrentVisited ABCDEFGH

Did you like this challenge?

Click on a star to rate it!

Average rating 4.6 / 5. Vote count: 32

No votes so far! Be the first to rate this post.

As you found this challenge interesting...