Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]= 29, d[u]= 15, w[u,v]=12. What is the updated value of d[v] based on current information?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. 27
Explanation
d[v] = min(29, d[u] + w(u, v)) = min(29, 15 + 12) = 27.
More Data Structures and Algorithms questions
- When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?
- 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…