Dijkstra's Shortest Path Algorithm (OCR A-Level Computer Science): Quizzes
📚Quizzes
Practise the questions
15 questions from this quiz
ShowHide
Practise the questions
15 questions from this quiz
What type of edge weights must a graph have for Dijkstra's algorithm to guarantee the shortest path?
What type of edge weights must a graph have for Dijkstra's algorithm to guarantee the shortest path?
Non-negative weights
What is the initial distance value set for the source node in Dijkstra's algorithm?
What is the initial distance value set for the source node in Dijkstra's algorithm?
What is the initial distance value set for all non-source nodes in Dijkstra's algorithm?
What is the initial distance value set for all non-source nodes in Dijkstra's algorithm?
Infinity ()
What type of algorithm is Dijkstra's shortest path algorithm?
What type of algorithm is Dijkstra's shortest path algorithm?
Greedy algorithm
What is the time complexity of Dijkstra's algorithm using an adjacency matrix?
What is the time complexity of Dijkstra's algorithm using an adjacency matrix?
What is the time complexity of Dijkstra's algorithm with a priority queue using a binary heap?
What is the time complexity of Dijkstra's algorithm with a priority queue using a binary heap?
What is the space complexity for Dijkstra's algorithm using an adjacency list?
What is the space complexity for Dijkstra's algorithm using an adjacency list?
Which unvisited node should be selected next in Dijkstra's algorithm?
Which unvisited node should be selected next in Dijkstra's algorithm?
Node with smallest tentative distance
What happens to a node after all its neighbours are evaluated in Dijkstra's algorithm?
What happens to a node after all its neighbours are evaluated in Dijkstra's algorithm?
Marked as visited, not revisited
In the example, what is the shortest distance from A to B?
In the example, what is the shortest distance from A to B?
(via C)
In the example, what is the total distance of the shortest path from A to E?
In the example, what is the total distance of the shortest path from A to E?
In the tracing example, what is the distance from A to C?
In the tracing example, what is the distance from A to C?
(via B)
What is a common mistake when implementing Dijkstra's algorithm regarding initialisation?
What is a common mistake when implementing Dijkstra's algorithm regarding initialisation?
Forgetting to set source distance to
What problem occurs if already visited nodes are revisited in Dijkstra's algorithm?
What problem occurs if already visited nodes are revisited in Dijkstra's algorithm?
Incorrect or inefficient execution
In the tracing example, what is the final distance from A to E?
In the tracing example, what is the final distance from A to E?
(via D)