# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

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

True | |

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?

While loop gets executed for v times | |

While loop gets executed for v-1 times | |

While loop gets executed only once | |

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?

8 | |

9 | |

4 | |

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-b-e | |

a-c-e | |

a-c-d-e | |

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

Greedy algorithm | |

Branch and bound | |

Back tracking | |

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.