Dijkstra’s Algorithm Multiple choice Questions and Answers (MCQs)

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

Dijkstra's Algorithm Multiple choice Questions and Answers (MCQs)

Question 6 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
How many priority queue operations are involved in Dijkstra's Algorithm?
A
1
B
3
C
2
D
4
Question 6 Explanation: 
The number of priority queue operations involved is 3. They are insert, extract-min and decrease key.

Question 7 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
How many times the insert and extract min operations are invoked per vertex?
A
1
B
2
C
3
D
0
Question 7 Explanation: 
Insert and extract min operations are invoked only once per vertex because each vertex is added only once to the set and each edge in the adjacency list is examined only once during the course of algorithm.

Question 8 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to .....
A
Total number of vertices
B
Total number of edges
C
Number of vertices - 1
D
Number of edges - 1
Question 8 Explanation: 
If the total number of edges in all adjacency list is E, then there will be a total of E number of iterations, hence there will be a total of at most E decrease key operations.

Question 9 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What is running time of Dijkstra's algorithm using Binary min- heap method?
A
O(V)
B
O(VlogV)
C
O(E)
D
O(ElogV)
Question 9 Explanation: 
Time required to build a binary min heap is O(V). Each decrease key operation takes O(logV) and there are still at most E such operations. Hence total running time is O(ElogV).

Question 10 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
The running time of Bellmann Ford algorithm is lower than that of Dijkstra's Algorithm.
A
True
B
False
Question 10 Explanation: 
The number of iterations involved in Bellmann Ford Algorithm is more than that of Dijkstra's Algorithm.

There are 10 questions to complete.