All-Pairs Shortest Paths. We have seen two algorithms that solve the All-Pairs S

Question

All-Pairs Shortest Paths. We have seen two algorithms that solve the All-Pairs
Shortest Paths problem using a dynamic programming approach. Answer the questions below
using simple textual descriptions.

(a) In the recursive solution described in Section 25.1, describe the key idea used
to characterize the structure of an optimal solution and how it is used in order to achieve
a recursive definition.

(b) The recursive solution requires several iterations in order for the nal L matrix
to be computed. What is the maximum number of iterations needed and why?

(c) Describe what is the key concept used to improve the running time of the
recursive solution algorithm.

(d) In the Floyd-Warshall algorithm, describe the key idea used to characterize
the structure of an optimal solution and how it is used in order to achieve a recursive
de nition.

(16 points) AllPairs Shortest Paths. We have seen two algorithms that solve the Al-Pairs Shortest Paths problem using a dynamic programming approach. Answer the questions below using simple textual descriptions (a (4 points) In the recursive solution described in Section 25.1, describe the key idea used to characterize the structure of an optimal solution and how it is used in order to achieve a recursive definition. (b) (4 points) The recursive solution requires several iterations in order for the final L matrix to be computed. What is the maximum number of iterations needed and why? (c) (4 points) Describe what is the key concept used to improve the running time of the recursive solution algorithm. (d) (4 points) In the Floyd-Warshall algorithm, describe the key idea used to characterize the structure of an optimal solution and how it is used in order to achieve a recursive definition.

Explanation / Answer

(a)

four steps:

1. Characterize the structure of an optimal solution.

2. Recursively define the value of an optimal solution.

3. Compute the value of an optimal solution, typically in a bottom-up fashion.

4. Construct an optimal solution from computed information.

(b)maximum iteration required O(n3) wher n is the number of matrix.

(c)

The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key, for example, to Karatsuba's fast multiplication method, the quicksort and mergesort algorithms, the Strassen algorithm for matrix multiplication, and fast Fourier transforms.

In all these examples, the D&C approach led to an improvement in the asymptotic cost of the solution.

(d)We initialize the solution matrix same as the input graph matrix as a first step. Then we update the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and update all shortest paths which include the picked vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every pair (i, j) of source and destination vertices respectively, there are two possible cases.
1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.
2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j].

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.