Optimisation Algorithms

Question 1

Dijkstras Shortest Path algorithm

Answer 1

Find the shortest path between a starting node and every other node in a WEIGHTED graph

Supporting data structure - priority queue

Question 2

What happens when the priority queue is not empty?

Answer 2

Remove the node at the front of the queue

This node is referred to as the current node.

Question 3

What is done with each neighbour of the current node?

Answer 3

Compute new distance by adding together the temporary distance at the current node and the length of the edge going to that neighbour

This calculation helps to determine if a shorter path exists.

Question 4

What condition must be met to replace a neighbour’s distance?

Answer 4

If the new distance is less than the neighbour’s current distance

This ensures that only shorter paths are considered.

Question 5

Fill in the blank: The current node is removed from the priority queue and is referred to as the _______.

Answer 5

[current node]