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

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

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

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

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

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)

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)

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; }

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

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

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

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

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

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

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

13. Consider the following graph.

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

14. In the given graph, identify the shortest path having minimum cost to reach vertex E if A is the source vertex.

a) a-b-e
b) a-c-e
c) a-c-d-e
d) a-c-d-b-e
View Answer

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

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.