4.

Dynamic Programming
Contents
• General Method
• All Pairs Shortest Paths
• Multistage graphs
• Optimal binary search tree
• String editing
• 0/1 Knapsack
• Reliability Design.
General Method
• Dynamic programming is an algorithm design method that can be used when
the solution to a problem can be viewed as the result of a sequence of decisions.
• Examples:
• The solution to the knapsack problem can be viewed as the result of a
sequence of decisions, to decide the value of xi. An optimal sequence of
decisions maximizes the objective function.
• An optimal merge pattern tells us which pair of files should be merged at each
step. As a decision sequence, the problem calls for us to decide which pair of
files should be merged first, which pair second, which pair third, and so on. An
optimal sequence of decisions is a least-cost sequence.
General Method
• For some of the problems, an optimal sequence of decisions can be found by making
the decisions one at a time and never making an erroneous decision. This is true for
all problems solvable by the greedy method.
• For many other problems, it is not possible to make stepwise decisions in such a
manner that the sequence of decisions made is optimal.
• One way to solve such problems is to try all possible decision sequences.
• Enumerate all decision sequences and then pick out the best. But the time and space
requirements may be prohibitive.
• Dynamic programming often drastically reduces the amount of enumeration by
avoiding the enumeration of some decision sequences that cannot possibly be
optimal.
• In dynamic programming an optimal sequence of decisions is obtained by making
explicit appeal to the principle of optimality.
General Method - Principle of optimality
• The principle of optimality states that an optimal sequence of decisions has the
property that whatever the initial state and decision are, the remaining decisions
must constitute an optimal decision sequence with regard to the state resulting from
the first decision.
• In the greedy method only one decision sequence is ever generated.
• In dynamic programming, many decision sequences may be generated.
•
Dynamic Programming Design Bottom Up
Approach
• Dynamic programming design involves 4 major steps:
1. Characterize the structure of optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution in a bottom up fashion
4. Construct an optimum solution for computed information.
All pairs shortest paths
• Let G = (V, E) be a directed graph with n vertices.
• Let cost be a cost adjacency matrix for G such that cost(i, i) = 0, 1 ≤ i ≤ n.
• Then cost(i, j) is the length (or cost) of edge <i,j> if (i,j) € E(G) and cost(i,j) = ∞
if I ≠ j and (i,j) € E(G).
• The all-pairs shortest-path problem is to determine a matrix A such that A(i,j) is the
length of a shortest path from i to j.
• The matrix A can be obtained by solving n single-source problems using the
algorithm ShortestPaths.
• Since each application of this procedure requires O(n2) time, the matrix A can be
obtained in O(n3) time
All pairs shortest paths
• A shortest path from i to j path in G, i ≠ j can be examined as,
• The path originates at vertex i and goes through some intermediate vertices and
terminates at vertex j.
• If k is an intermediate vertex on this shortest path, then the subpaths from i to k and
from k to j must be shortest paths from i to k and k to j, respectively.
• Otherwise, the i to j path is not of minimum length. So, the principle of optimality
holds.
• Using Ak(i,j) to represent the length of a shortest path from i to j going through no
vertex of index greater than k, we obtain
All pairs shortest paths
• A shortest path from i to j going through no vertex higher than k either goes through
vertex k or it does not. If it does, Ak(i,j) = Ak- 1 (i , k )+ Ak- 1 ( k , j ). Combining we get,
All pairs shortest paths Example
Example Contd..
A shortest path can be computed using,
AK(i,j) = W(i,j), if k = 0
= min { Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j)}, if k>=1

Initially calculate Cost Adjacency Matrix,

A0(i,j) = W(i,j) =
Example Contd..
A shortest path can be computed using,
AK(i,j) = W(i,j), if k = 0
= min { Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j)}, if k>=1

Step 1: For K = 1, i.e., going from i to j through intermediate vertex k = 1.

Calculate, A1(i,j)
i=1 //{i =1, j=1,2,3, k=1}
Source 1 to Dest 1,2,3 via intermediate Vertex 1 → Shortest Path
A1(1,1) = min{A0{1,1}, A0{1,1)+A0(1,1)} = 0
A1(1,2) = min{A0(1,2), A0(1,1) + A0(1,2)} = min{4, 0+4} = 4
A1(1,3) = min{A0(1,3), A0(1,1) + A0(1,3)} = min{11, 0+11} = 11
Example Contd.. i = 2 //{i =2, j=1,2,3, k=1}
Source 3 to Dest 1,2,3 via intermediate Vertex 1 → Shortest Path
A1(2,1) = min{A0(2,1), A0(2,1)+A0(1,1)} = min{6, 6 + 0} = 6
A1(2,2) = min{A0(2,2), A0(2,1) + A0(1,2)} = min{0, 6+4} = 0
A1(2,3) = min{A0(2,3), A0(2,1) + A0(1,3)} = min{2, 6+11} = 2
i=3 //{i =3, j=1,2,3, k=1}
Source 3 to Dest 1,2,3 via intermediate Vertex 1 → Shortest Path
A1(3,1) = min{A0(3,1), A0(3,1)+A0(1,1)} = min{3, 3 + 0} = 3
A1(3,2) = min{A0(3,2), A0(3,1) + A0(1,2)} = min{∞, 3+4} = 7
A1(3,3) = min{A0(3,3), A0(3,1) + A0(1,3)} = min{0, 3+11} = 0

→
Example Contd..
A shortest path can be computed using,
AK(i,j) = W(i,j), if k = 0
= min { Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j)}, if k>=1

Step 2: For K = 2, i.e., going from i to j through intermediate vertex k = 2.

Calculate, A2(i,j)
i=1 {i = 1, j = 1,2,3, k = 2}
Source 1 to Destination 1,2,3 via intermediate Vertex 2 → Shortest Path
A2(1,1) = min{A1(1,1), A1(1,2)+A1(2,1)} = min{0, 4 + 6} = 0
A2(1,2) = min{A1(1,2), A1(1,2) + A1(2,2)} = min{4, 4 + 0} = 4
A2(1,3) = min{A1(1,3), A1(1,2) + A1(2,3)} = min{11, 4 + 2} = 6
Example Contd.. i=2 {i = 2, j = 1,2,3, k = 2}
Source 2 to Destination 1,2,3 via intermediate Vertex 2 → Shortest Path
A2(2,1) = min{A1(2,1), A1(2,2)+A1(2,1)} = min{6, 0 + 6} = 6
A2(2,2) = min{A1(2,2), A1(2,2) + A1(2,2)} = min{0, 0 + 0} = 0
A2(2,3) = min{A1(2,3), A1(2,2) + A1(2,3)} = min{2, 0 + 2} = 2
i=3 {i = 3, j = 1,2,3, k = 2}
Source 3 to Destination 1,2,3 via intermediate Vertex 2 → Shortest Path
A2(3,1) = min{A1(3,1), A1(3,2)+A1(2,1)} = min{3, 7 + 6 } = 3
A2(3,2) = min{A1(3,2), A1(3,2) + A1(2,2)} = min{7, 7 + 0} = 7
A2(3,3) = min{A1(3,3), A1(3,2) + A1(2,3)} = min{0, 7 + 2} = 0

→
Example Contd..
A shortest path can be computed using,
AK(i,j) = W(i,j), if k = 0
= min { Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j)}, if k>=1

Step 3: For K = 3, i.e., going from i to j through intermediate vertex k = 3.

Calculate, A3(i,j)
i=1 {i = 1, j = 1,2,3, k = 3}
Source 1 to Destination 1,2,3 via intermediate Vertex 2 → Shortest Path
A2(1,1) = min{A1(1,1), A1(1,3)+A1(3,1)} = min{0, 6 + 3} = 0
A2(1,2) = min{A1(1,2), A1(1,3) + A1(3,2)} = min{4, 6 + 7} = 4
A2(1,3) = min{A1(1,3), A1(1,3) + A1(3,3)} = min{6, 6 + 0} = 6
Example Contd.. i=2 {i = 2, j = 1,2,3, k = 3}
Source 2 to Destination 1,2,3 via intermediate Vertex 3 → Shortest Path
A2(2,1) = min{A1(2,1), A1(2,3)+A1(3,1)} = min{6, 2 + 3} = 5
A2(2,2) = min{A1(2,2), A1(2,3) + A1(3,2)} = min{0, 2 + 7} = 0
A2(2,3) = min{A1(2,3), A1(2,3) + A1(3,3)} = min{2, 2 + 2} = 2
i=3 {i = 3, j = 1,2,3, k = 3}
Source 3 to Destination 1,2,3 via intermediate Vertex 3 → Shortest Path
A2(3,1) = min{A1(3,1), A1(3,3)+A1(3,1)} = min{3, 0 + 3 } = 3
A2(3,2) = min{A1(3,2), A1(3,3) + A1(3,2)} = min{7, 0 + 7} = 7
A2(3,3) = min{A1(3,3), A1(3,3) + A1(3,3)} = min{0, 0 + 0} = 0

→
Algorithm

The time needed by AIIPaths Algorithm is especially easy

to determine because the looping is independent of the
data in the matrix A. Line 11 is iterated n3 times, and so
the time for AIIPaths is O(n3) .
Homework
• Find the shortest paths between every pair of nodes for the following graph using
dynamic programming approach:

4
1 2

7 8
6

3
2 3
5