When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. Shortest path always passes through least number of vertices
Explanation
Dijkstra finds the cheapest path, not the one with the fewest vertices, so C is false. It always visits the closest unvisited node next and needs non-negative weights.
More Data Structures and Algorithms questions
- The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is :
- The following multithreaded algorithm computes transpose of a matrix in parallel : p Trans (X, Y, N) if N = 1 ← then Y[1,1] X[1,1] else par…
- Consider the following statements : (a) The running time of dynamic programming θ(ρ) ρ algorithm is alway where is number of subproblems. (…
- With preconditions p ≥ 1 and n ≥ 0 (no overflow): int x = p; int k = n; int m = 1; while (k != 0) { if (k is odd) m = m * x; x = x * x; k =…
- Match List I with List II. List I: (a) Prim's algorithm, (b) Dijkstra's algorithm, (c) Faster all-pairs shortest path, (d) Edmonds-Karp alg…
- There are many sorting algorithms based on comparison. The running time of heapsort O(n lg n) P Q algorithm is . Like , but unlike , (P, Q)…