Dynamic programming algorithms for all-pairsshortest path and longest common subsequencesWe will study a new techniquedynamic programmingalgorithms (typically for optimization problems).Ideas:- Characterize the structure of an optimal solution- Recursively define the value of an optimal solution- Compute the value of an optimal solution in a bottom-up fashion (using matrix to compute)- Backtracking to construct an optimal solution fromcomputedinformation
Dynamic programming algorithms for all-pairs shortest path and longest common subsequences • We will study a new technique—dynamic programming algorithms (typically for optimization problems) • Ideas: – Characterize the structure of an optimal solution – Recursively define the value of an optimal solution – Compute the value of an optimal solution in a bottom- up fashion (using matrix to compute) – Backtracking to construct an optimal solution from computed information
Floyd-Warshall algorithm forshortest path:: Use a different dynamic-programmingformulation to solve the all-pairs shortest-pathsproblem on a directed graph G=(V,E).The resulting algorithm, known as the Floyd-Warshall algorithm, runs in O (V3) time- negative-weight edges may be present.- but we shall assume that there are no negative.weight cycles
Floyd-Warshall algorithm for shortest path: • Use a different dynamic-programming formulation to solve the all-pairs shortest-paths problem on a directed graph G=(V,E). • The resulting algorithm, known as the Floyd- Warshall algorithm, runs in O (V3) time. – negative-weight edges may be present, – but we shall assume that there are no negative- weight cycles
The structure of a shortest path:We use a different characterization of the structure of ashortest path than we used in the matrix-multiplication-based all-pairs algorithms.The algorithm considers the intermediate"' vertices of ashortest path, where an intermediate vertex of a simplepath p=<Vi,V2,...,Vi> is any vertex in p other than Vi or Vi,that is, any vertex in the set {V2,V3,...,Vi-1]
The structure of a shortest path: • We use a different characterization of the structure of a shortest path than we used in the matrix-multiplication- based all-pairs algorithms. • The algorithm considers the “intermediate” vertices of a shortest path, where an intermediate vertex of a simple path p=<v1 ,v2 ,.,vl> is any vertex in p other than v1 or vl, that is, any vertex in the set {v2 ,v3 ,.,vl-1}
Continue:: Let the vertices ofG be V=(1,2,... ,n}, and consider asubset {1,2,...,k} of vertices for some k.For any pair of vertices i.j e V, consider all paths from i toj whose intermediate vertices are all drawn from1,2,... ,k},and let p be a minimum-weight path fromamong them.The Floyd-Warshall algorithm exploits a relationshipbetween path p and shortest paths from i to j with allintermediate vertices in the set (1,2,... ,k-1)
Continue: • Let the vertices of G be V={1,2,.,n}, and consider a subset {1,2,.,k} of vertices for some k. • For any pair of vertices i,j V, consider all paths from i to j whose intermediate vertices are all drawn from {1,2,.,k},and let p be a minimum-weight path from among them. • The Floyd-Warshall algorithm exploits a relationship between path p and shortest paths from i to j with all intermediate vertices in the set {1,2,.,k-1}
Relationship:The relationship depends on whether or not k is anintermediate vertex of path p If k is not an intermediate vertex of path p, then allintermediate vertices of path p are in the set 1,2,... ,k-1}Thus, a shortest path from vertex i to vertex j with allintermediate vertices in the set 1,2,... ,k-1 is also ashortest path from i to j with all intermediate vertices in theset {1,2,...,k).If k is an intermediate vertex of path p,then we break pkdown into ij as shown Figure 2.pl is ashortest path from i to k with all intermediate vertices inthe set (1,2,... ,k-11, so as p2
Relationship: • The relationship depends on whether or not k is an intermediate vertex of path p. • If k is not an intermediate vertex of path p, then all intermediate vertices of path p are in the set {1,2,.,k-1}. Thus, a shortest path from vertex i to vertex j with all intermediate vertices in the set {1,2,.,k-1} is also a shortest path from i to j with all intermediate vertices in the set {1,2,.,k}. • If k is an intermediate vertex of path p,then we break p down into i k j as shown Figure 2.p1 is a shortest path from i to k with all intermediate vertices in the set {1,2,.,k-1}, so as p2