When using Dijkstra’s algorithm to find shortest path in a graph, which of the…
2019
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
Attempted by 481 students.
Show answer & explanation
Correct answer: C
Answer: 'Shortest path always passes through least number of vertices' is not true.
Reasoning:
Definition: A shortest path minimizes the total sum of edge weights (total cost), not the number of vertices or edges.
Counterexample: Consider two paths from node A to node B: a direct edge A–B with weight 10 (one edge), and a two-edge path A–C–B with weights 3 and 3. The two-edge path has total weight 6, which is shorter even though it passes through more vertices.
Dijkstra’s key properties:
It is a single-source shortest-path algorithm that repeatedly selects the unvisited vertex with the smallest tentative distance and relaxes its outgoing edges.
It requires non-negative edge weights; negative edges can invalidate the assumption that a visited vertex has its final shortest distance.
It runs on the given graph structure to compute shortest paths from a chosen source to other vertices (or to a target if stopped early).
Conclusion: The false statement is the claim that shortest paths always use the fewest vertices; shortest paths minimize total weight, not edge count.
A video solution is available for this question — log in and enroll to watch it.