What is the correct recurrence relation for all pair shortest path using…
What is the correct recurrence relation for all pair shortest path using floyd-warshall algorithm is?
Answer: A. AK(i, j) = min{ AK-1(i, K) + AK-1(K, j), AK-1(i, j)} — Interpretation: A_k(i, j) denotes the length of the shortest path from i to j whose intermediate vertices (if any) are all in the set {1,...,k}. Recurrence:…
- A.
AK(i, j) = min{ AK-1(i, K) + AK-1(K, j), AK-1(i, j)}
- B.
AK(i, j) = min{ AK+1(i, K) + AK+1(K, j), Ak+1(i, j)}
- C.
AK(i, j) = min{ Aj-1(i, K) + Aj-1(K, j), Aj-1(i, j)}
- D.
AK(i, j) = min{ Aj+1(i, K) + Aj+1(K, j), Aj+1(i, j)}
Attempted by 166 students.
Show answer & explanation
Correct answer: A
Interpretation: A_k(i, j) denotes the length of the shortest path from i to j whose intermediate vertices (if any) are all in the set {1,...,k}.
Recurrence: A_k(i, j) = min(A_{k-1}(i, j), A_{k-1}(i, k) + A_{k-1}(k, j)).
Base case: A_0(i, j) is the direct edge weight from i to j (use 0 for i = j and infinity if there is no direct edge).
Meaning of the two terms: The first term A_{k-1}(i,j) is the shortest path that does not use vertex k; the second term A_{k-1}(i,k) + A_{k-1}(k,j) is the length of a path that goes from i to j via k (with intermediates from {1,...,k-1}).
Iteration: Run k from 1 to n to progressively allow more intermediate vertices; after k = n, A_n(i,j) is the shortest path between i and j using any vertices.