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

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Dijkstra’s Algorithm”.

1. Dijkstra’s Algorithm is used to solve _____________ problems.
a) All pair shortest path
b) Single source shortest path
c) Network flow
d) Sorting
View Answer

Answer: b
Explanation: Dijkstra’s Algorithm is used for solving single source shortest path problems. In this algorithm, a single node is fixed as a source node and shortest paths from this node to all other nodes in graph is found.

2. Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?
a) Max priority queue
b) Stack
c) Circular queue
d) Min priority queue
View Answer

Answer: d
Explanation: Minimum priority queue is the most commonly used data structure for implementing Dijkstra’s Algorithm because the required operations to be performed in Dijkstra’s Algorithm match with specialty of a minimum priority queue.

3. What is the time complexity of Dijikstra’s algorithm?
a) O(N)
b) O(N3)
c) O(N2)
d) O(logN)
View Answer

Answer: c
Explanation: Time complexity of Dijkstra’s algorithm is O(N2) because of the use of doubly nested for loops. It depends on how the table is manipulated.
advertisement
advertisement

4. Dijkstra’s Algorithm cannot be applied on ______________
a) Directed and weighted graphs
b) Graphs having negative weight function
c) Unweighted graphs
d) Undirected and unweighted graphs
View Answer

Answer: b
Explanation: Dijkstra’s Algorithm cannot be applied on graphs having negative weight function because calculation of cost to reach a destination node from the source node becomes complex.

5. What is the pseudo code to compute the shortest path in Dijkstra’s algorithm?
a)

Note: Join free Sanfoundry classes at Telegram or Youtube
if(!T[w].Known)
 	if(T[v].Dist + C(v,w) < T[w].Dist)  {
                 Decrease(T[w].Dist to T[v].Dist +C(v,w));
                T[w].path=v; }

b)

advertisement
if(T[w].Known)
 	if(T[v].Dist + C(v,w) < T[w].Dist)  {
                 Increase (T[w].Dist to T[v].Dist +C(v,w));
                T[w].path=v; }

c)

advertisement
if(!T[w].Known)
 	if(T[v].Dist + C(v,w) > T[w].Dist)  {
                 Decrease(T[w].Dist to T[v].Dist +C(v,w);
                  T[w].path=v; }

d)

if(T[w].Known)
 	if(T[v].Dist + C(v,w) < T[w].Dist)  {
                 Increase(T[w].Dist to T[v].Dist);
                T[w].path=v; }
View Answer
Answer: a
Explanation: If the known value of the adjacent vertex(w) is not set then check whether the sum of distance from source vertex(v) and cost to travel from source to adjacent vertex is less than the existing distance of the adjacent node. If so, perform decrease key operation.
 
 

6. How many priority queue operations are involved in Dijkstra’s Algorithm?
a) 1
b) 3
c) 2
d) 4
View Answer

Answer: b
Explanation: The number of priority queue operations involved is 3. They are insert, extract-min and decrease key.

7. How many times the insert and extract min operations are invoked per vertex?
a) 1
b) 2
c) 3
d) 0
View Answer

Answer: a
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.

8. 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
View Answer

Answer: b
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.

9. 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)
View Answer

Answer: d
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).

10. The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.
a) True
b) False
View Answer

Answer: b
Explanation: The number of iterations involved in Bellmann Ford Algorithm is more than that of Dijkstra’s Algorithm.

11. Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V.
a) True
b) False
View Answer

Answer: a
Explanation: The equality d[u]=delta(s,u) holds good when vertex u is added to set S and this equality is maintained thereafter by the upper bound property.

12. Given pseudo code of Dijkstra’s Algorithm.

//Initialise single source(G,s)
S=0
Q=V[G]
While Q != 0
    Do u=extract-min(Q)
        S=S union {u}
	    For each vertex v in adj[u]
	        Do relax(u,v,w)

What happens when “While Q != 0” is changed to “while Q>1”?
a) While loop gets executed for v times
b) While loop gets executed for v-1 times
c) While loop gets executed only once
d) While loop does not get executed
View Answer

Answer: b
Explanation: In the normal execution of Dijkstra’s Algorithm, the while loop gets executed V times. The change in the while loop statement causes it to execute only V – 1 times.

13. Consider the following graph.
The minimum cost to reach f vertex is 6 if b is the source vertex
If b is the source vertex, what is the minimum cost to reach f vertex?
a) 8
b) 9
c) 4
d) 6
View Answer

Answer: d
Explanation: The minimum cost to reach f vertex from b vertex is 6 by having vertices g and e as intermediates.
b to g, cost is 1
g to e, cost is 4
e to f, cost is 1
hence total cost 1+4+1=6.

14. In the given graph, identify the shortest path having minimum cost to reach vertex E if A is the source vertex.
Shortest path having minimum cost to reach vertex E if A is source vertex is a-c-e
a) a-b-e
b) a-c-e
c) a-c-d-e
d) a-c-d-b-e
View Answer

Answer: b
Explanation: The minimum cost required to travel from vertex A to E is via vertex C
A to C, cost= 3
C to E, cost= 2
Hence the total cost is 5.

15. Dijkstra’s Algorithm is the prime example for ___________
a) Greedy algorithm
b) Branch and bound
c) Back tracking
d) Dynamic programming
View Answer

Answer: a
Explanation: Dijkstra’s Algorithm is the prime example for greedy algorithms because greedy algorithms generally solve a problem in stages by doing what appears to be the best thing at each stage.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.