Shortest Path Algorithms (Edexcel A-Level Further Mathematics): Quizzes
📚Quizzes
Practise the questions
10 questions from this quiz
ShowHide
Practise the questions
10 questions from this quiz
What does Dijkstra's algorithm find in a weighted graph?
What does Dijkstra's algorithm find in a weighted graph?
Shortest path from start to all nodes
In initialization, what distance is assigned to the starting node?
In initialization, what distance is assigned to the starting node?
In initialization, what distance is assigned to all other nodes?
In initialization, what distance is assigned to all other nodes?
(infinity)
How is tentative distance to a neighbour calculated?
How is tentative distance to a neighbour calculated?
Current node distance + edge weight
When should a neighbour's tentative distance be updated?
When should a neighbour's tentative distance be updated?
When new distance is less than current
What happens to a node after all its neighbours are examined?
What happens to a node after all its neighbours are examined?
Marked as visited, not checked again
How is the next current node selected?
How is the next current node selected?
Unvisited node with smallest distance
When does Dijkstra's algorithm terminate?
When does Dijkstra's algorithm terminate?
All nodes visited or target found
Which common mistake involves treating edges incorrectly?
Which common mistake involves treating edges incorrectly?
Treating all edges as equal weight