2.3.1 - Algorithms (Shortest Path)

Question 1

Perform Dijkstra’s on the following graph to find the shortest path between A and H

Answer 1

Question 2

Perform A* on the following graph to find the shortest path between A and Z

Answer 2

Question 3

What are the key facts about the Dijkstra’s algorithm?

Answer 3

• Uses a weight/distance
• Will always visit every node
• Finds the most efficient route

Question 4

What are the key facts about the A* algorithm?

Answer 4

• Uses an estimated distance from final node called a heuristic, this helps produce a solution in a faster time.
• Chooses which path to take next based on lowest total distance travelled
• Doesn’t need to find all possible solutions (saves time)