Q. If a graph has V vertices and E edges, what is the space complexity of Dijkstra's algorithm?
A.
O(V)
B.
O(E)
C.
O(V + E)
D.
O(V^2)
Show solution
Solution
The space complexity of Dijkstra's algorithm is O(V + E) due to the storage of the graph's adjacency list and the distance array.
Correct Answer:
C
— O(V + E)
Learn More →
Q. In Dijkstra's algorithm, what data structure is primarily used to keep track of the shortest path estimates?
A.
Array
B.
Linked List
C.
Stack
D.
Priority Queue
Show solution
Solution
A priority queue is used in Dijkstra's algorithm to efficiently retrieve the vertex with the smallest distance estimate.
Correct Answer:
D
— Priority Queue
Learn More →
Q. In the context of Dijkstra's algorithm, what does the term 'relaxation' refer to?
A.
Updating the priority queue
B.
Calculating the shortest path
C.
Updating the distance estimate of a vertex
D.
Removing a vertex from the graph
Show solution
Solution
Relaxation refers to the process of updating the distance estimate of a vertex when a shorter path is found.
Correct Answer:
C
— Updating the distance estimate of a vertex
Learn More →
Q. What is the primary purpose of the 'visited' set in Dijkstra's algorithm?
A.
To store the shortest path
B.
To avoid processing the same vertex multiple times
C.
To keep track of the edges
D.
To maintain the priority queue
Show solution
Solution
The 'visited' set is used to avoid processing the same vertex multiple times, ensuring that each vertex is only processed once.
Correct Answer:
B
— To avoid processing the same vertex multiple times
Learn More →
Q. What is the worst-case time complexity of Dijkstra's algorithm when using an adjacency matrix?
A.
O(V^2)
B.
O(E log V)
C.
O(V log V)
D.
O(E + V log V)
Show solution
Solution
When using an adjacency matrix, the worst-case time complexity of Dijkstra's algorithm is O(V^2) because each vertex must be checked against all others.
Correct Answer:
A
— O(V^2)
Learn More →
Showing 1 to 5 of 5 (1 Pages)
