# 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.