UGC NET Computer Science December 2019 | Question 91

Question 91

---

When using Dijkstra's algorithm to find shortest path in a graph. which of the following statement is not true?

1. (1) It can find shortest path within the same graph data structure
2. (2) Every time a new node is visited. we choose the node with smallest known distance/cost (weight) to visit first
3. (3) Shortest path always passes through least number of vertices
4. (4) The graph needs to have a non-negative weight on every edge

Answer : (3) Shortest path always passes through least number of vertices

Explanation

Option (1) : TRUE : Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes within the same graph data structure. Dijkstra's algorithm is a greedy algorithm to identify shortest path.

Option (2) : TRUE : Every time a new node is visited, we choose the node with the smallest known distance/cost (weight) to visit first

Option (3) : FALSE : It is false because Shortest path can have any number of vertices.

Option (4) : TRUE : Dijkstra's algorithm will support only positive weight edges.

So, option 3 is correct answer

Reference : Dijkstra's algorithm (Dijkstra's Shortest Path First algorithm)

Previous	Next
UGC NET CS December 2019 - Question 90	UGC NET CS December 2019 - Question 92