Greedyapproach
October 26, 2023FunctionalDependency
October 26, 2023Greedyapproach
Question 5

When using Dijkstra’s algorithm to find shortest path in a graph, which of the following statement is not true?
It can find shortest path within the same graph data structure


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


Shortest path always passes through least number of vertices


The graph needs to have a nonnegative weight on every edge

Question 5 Explanation:
TRUE: Dijkstra’s algorithm always find shortest path with in the same graph data structure. It uses a greedy technique to identify shortest path.
TRUE: Every time a new node is visited, we choose the node with the smallest known distance/cost (weight) to visit first
FALSE: It is false because this algorithm applicable any number of vertices.
TRUE: Dijkstra’s algorithm will support only positive weight edges.
TRUE: Every time a new node is visited, we choose the node with the smallest known distance/cost (weight) to visit first
FALSE: It is false because this algorithm applicable any number of vertices.
TRUE: Dijkstra’s algorithm will support only positive weight edges.
Correct Answer: C
Question 5 Explanation:
TRUE: Dijkstra’s algorithm always find shortest path with in the same graph data structure. It uses a greedy technique to identify shortest path.
TRUE: Every time a new node is visited, we choose the node with the smallest known distance/cost (weight) to visit first
FALSE: It is false because this algorithm applicable any number of vertices.
TRUE: Dijkstra’s algorithm will support only positive weight edges.
TRUE: Every time a new node is visited, we choose the node with the smallest known distance/cost (weight) to visit first
FALSE: It is false because this algorithm applicable any number of vertices.
TRUE: Dijkstra’s algorithm will support only positive weight edges.
Subscribe
Login
0 Comments