Q. If a graph has V vertices and E edges, what is the worst-case time complexity of Dijkstra's algorithm using an adjacency matrix?
A.
O(V^2)
B.
O(E log V)
C.
O(V + E)
D.
O(V^3)
Solution
When using an adjacency matrix, the worst-case time complexity of Dijkstra's algorithm is O(V^2) because it requires checking all vertices for the minimum distance.
Q. In Dijkstra's algorithm, what does the priority queue store?
A.
All vertices
B.
Only visited vertices
C.
Only unvisited vertices
D.
Only the shortest path vertices
Solution
The priority queue in Dijkstra's algorithm stores only the unvisited vertices, allowing the algorithm to efficiently select the next vertex with the smallest tentative distance.
Q. What is the time complexity of Dijkstra's algorithm using a priority queue implemented with a binary heap?
A.
O(V^2)
B.
O(E log V)
C.
O(V log V)
D.
O(E + V)
Solution
Dijkstra's algorithm has a time complexity of O(E log V) when using a priority queue implemented with a binary heap, where E is the number of edges and V is the number of vertices.
