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 11 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 11 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.

Question 12 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Given pseudo code of Dijkstra's Algorithm.

1. //Initialise single source(G, s) 2. S=0 3. Q=V[G] 4. While Q != 0 5.	Do u=extract-min(Q) 6.		S=S union {u} 7.		For each vertex v in adj[u] 8.			Do relax(u, v, w)

What happens when while loop in line 4 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
Question 12 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.

Question 13 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Consider the following graph.

If b is the source verte, x what is the minimum cost to reach f vertex?

A
8
B
9
C
4
D
6
Question 13 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.

Question 14 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 14 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.

Question 15 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Dijkstra's Algorithm is the prime example for .....
A
Greedy algorithm
B
Branch and bound
C
Back tracking
D
Dynamic programming
Question 15 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.

There are 15 questions to complete.