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

## Dijkstra's Algorithm Multiple choice Questions and Answers (MCQs)

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Dijkstra's Algorithm is used to solve ..... problems.

All pair shortest path | |

Single source shortest path | |

Network flow | |

Sorting |

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

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Which of the following is the most commonly used data structure for implementing Dijkstra's Algorithm?

Max priority queue | |

Stack | |

Circular queue | |

Min priority queue |

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

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the time complexity of Dijikstra's algorithm?

O(N) | |

O(N ^{3}) | |

O(N ^{2}) | |

O(logN) |

Question 3 Explanation:

Time complexity of Dijkstra's algorithm is O(N

^{2}) because of the use of doubly nested for loops. It depends on how the table is manipulated.Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Dijkstra's Algorithm cannot be applied on .....

Directed and weighted graphs | |

Graphs having negative weight function | |

Unweighted graphs | |

Undirected and unweighted graphs |

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

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the pseudo code to compute the shortest path in Dijkstra's algorithm?

if(!T[w].Known) if(T[v].Dist + C(v, w) < T[w].Dist) { Decrease(T[w].Dist to | |

if(T[w].Known) if(T[v].Dist + C(v, w) < T[w].Dist) { Increase (T[w].Dist to T[ | |

if(!T[w].Known) if(T[v].Dist + C(v, w) > T[w].Dist) { Decrease(T[w].Dis | |

if(T[w].Known) if(T[v].Dist + C(v, w) < T[w].Dist) { Increase(T[w].Dist to T[v |

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

There are 5 questions to complete.