Q. If a graph has V vertices and E edges, what is the space complexity of Dijkstra's algorithm using an adjacency list?
-
A.
O(V)
-
B.
O(E)
-
C.
O(V + E)
-
D.
O(V^2)
Solution
The space complexity of Dijkstra's algorithm using an adjacency list is O(V + E) due to the storage of vertices and edges.
Correct Answer:
C
— O(V + E)
Learn More →
Q. In Dijkstra's algorithm, what data structure is primarily used to keep track of the minimum distance from the source vertex?
-
A.
Array
-
B.
Stack
-
C.
Queue
-
D.
Priority Queue
Solution
A priority queue is used in Dijkstra's algorithm to efficiently retrieve the vertex with the smallest distance from the source.
Correct Answer:
D
— Priority Queue
Learn More →
Q. What is the main advantage of using a Fibonacci heap with Dijkstra's algorithm?
-
A.
It reduces the space complexity.
-
B.
It improves the time complexity for decrease-key operations.
-
C.
It allows for negative weights.
-
D.
It simplifies the implementation.
Solution
Using a Fibonacci heap improves the time complexity for decrease-key operations, making Dijkstra's algorithm more efficient.
Correct Answer:
B
— It improves the time complexity for decrease-key operations.
Learn More →
Q. What is the primary limitation of Dijkstra's algorithm?
-
A.
It cannot find paths in directed graphs.
-
B.
It cannot handle negative weight edges.
-
C.
It is not efficient for dense graphs.
-
D.
It requires a complete graph.
Solution
Dijkstra's algorithm cannot handle negative weight edges, which can lead to incorrect results.
Correct Answer:
B
— It cannot handle negative weight edges.
Learn More →
Showing 1 to 4 of 4 (1 Pages)
