Greedy-approach

Question 5

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

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

AlgorithmsGreedy-approachUGC-NET DEC-2019 Part-2

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.

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.

Greedy-approach

Functional-Dependency

Greedy-approach

Functional-Dependency

Greedy-approach

Swmdwn Basumatary