DYNAMIC PROGRAMMING

GENERAL METHOD
Dynamic Programming is an algorithm design
method that can be used when the solution to a
problem may be viewed as the result of a
sequence of decisions.

The essential difference between the greedy

method and dynamic programming is that in the
greedy method only one decision sequence is
ever generated. In dynamic programming, many
decision sequences may be generated.
An optimal sequence of decisions is obtained by
principle of optimality.

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
MULTISTAGE GRAPHS
A multistage graph G = (V, E) is a directed graph
in which the vertices are partitioned into k>=2
disjoint sets Vi,1<=i <=k. In addition, if (u, v) is
an edge in E, then u∈Vi and v∈Vi+1 for some i,
1<=i< k. The sets
V1 and Vk are such that |V1| = |Vk| = 1.
Let s and t respectively be the vertex in V1 and
Vk .
Vertex s is the source and t the sink.
Let c(i, j) be the cost of edge (i,j). The cost of a
path from s to t is the sum of the costs of the
edges on the path.
The multistage graph problem is to find a
minimum cost path from s to t.

Each set Vi defines a stage in the graph. Because

of the constraints on E, every path from s tot
starts in stage 1, goes to stage 2, then to stage 3,
then to stage 4 etc. and eventually terminates in
stage k.

2 approaches:

Forward
Backward
Forward Approach
COST(1,1 ) = min{c(1,2) + Cost(2, 2), c(1,3) + Cost(2, 3),
c(1,4)+ Cost(2,4), c(1,5)+Cost(2,5)}
= min{9 + Cost(2, 2), 7+ Cost(2, 3), 3 + Cost(2,4),
2+Cost(2,5)}
= min{9+7, 7+9, 3+18, 2+15} = 16

COST(2,2 ) = min{c(2,6) + Cost(3, 6), c(2,7) + Cost(3, 7),

c(2,8)+ Cost(3,8)}
= min{4+ Cost(3, 6), 2 + Cost(3, 7), 1+ Cost(3,8)}
= min{4+7, 2+5, 1+7} = 7

COST(2,3 ) = min{c(3,6) + Cost(3, 6), c(3,7) + Cost(3, 7)}

= min{2+ Cost(3, 6), 7 + Cost(3, 7)}
= min{2+7, 7+5} = 9

COST(2,4 ) = min{c(4,8) + Cost(3, 8)}

= min{11+ Cost(3, 8)} =11+7 = 18

COST(2,5) = min{c(5,7) + Cost(3, 7), c(5,8) + Cost(3,8)}

= min{11+ Cost(3, 7), 8+Cost(3,8)}
= min{11+5, 8+7} = 15
COST(3,6 ) = min{c(6,9) + Cost(4, 9), c(6,10) + Cost(4, 10)}
= min{6+ Cost(4, 9), 5 + Cost(4, 10)}
= min{6+ 4, 5+ 2} = 7

COST(3,7 ) = min{c(7,9) + Cost(4, 9), c(7,10) + Cost(4, 10)}

= min{4+ Cost(4, 9), 3 + Cost(4, 10)}
= min{4+4, 3+2}= 5

COST(3,8 ) = min{c(8,10) + Cost(4, 10), c(8,11) + Cost(4, 11)}

= min{5+ Cost(4, 10), 6 + Cost(4, 11)}
= min{5+2, 6+5) = 7

COST(4,9 ) = min{c(9,12) + Cost(5, 12)}

= min{4+0}=4

COST(4,10 ) = min{c(10,12) + Cost(5, 12)}

= min{2+0}=2

COST(4,11 ) = min{c(11,12) + Cost(5, 12)}

= min{5+0}=5
Let d(i, j) be the value of l which minimizes

c(j, l) + COST(i + 1, l)

V2= d(1, V1)= d(1,1)= 2

V3= d(2, V2)= d(2,2) =7
V4 = d(3, V3) = d(3, 7) = 10

Therefore shortest path is 1-2-7-10-12

Minimum cost = 9+2+3+2= 16
If G has |E| edges then the time for the first for
loop is Ө(|V| + |E|).

The time for the second for loop is Ө(k ). Hence,

the total time in Ө (|V| + |E|).

In addition to the space needed for the input, space

is needed for Cost[ ], d[ ] and p[ ].
Backward Approach

Refer to fig. 5.2

bcost(5,12) = min{bcost(4,9)+c(9,12), bcost(4,10)+c(10,12),

bcost(4,11)+c(11,12)}
= min{bcost(4,9)+4, bcost(4,10)+2,
bcost(4,11)+5}
= min{15+4, 14+2, 16+5} =16
bcost(4,9) = min{bcost(3,6)+c(6,9), bcost(3,7)+c(7,9)}
= min{bcost(3,6)+6, bcost(3,7)+4}=min{9+6, 11+4} = 15
bcost(4,10) = min{bcost(3,6)+c(6,10), bcost(3,7)+c(7,10),
bcost(3,8)+c(8,10)}
= min{bcost(3,6)+5, bcost(3,7)+3,
bcost(3,8)+5} = min{9+5, 11+3,10+5} = 14
bcost(4,11) = min{bcost(3,8)+c(8,11)}
= min{bcost(3,8)+6} =min{10+6} = 16

bcost(3,6) = min{bcost(2,2)+c(2,6), bcost(2,3)+c(3,6)}

= min{bcost(2,2)+4, bcost(2,3)+2}= min{9+4, 7+2} = 9

bcost(3,7) = min{bcost(2,2)+c(2,7), bcost(2,3)+c(3,7),

bcost(2,5)+c(5,7)}
= min{bcost(2,2)+2, bcost(2,3)+7,
bcost(2,5)+11} = min{9+2, 7+7, 2+11} =11

bcost(3,8) = min{bcost(2,2)+c(2,8), bcost(2,4)+c(4,8),

bcost(2,5)+c(5,8)}
= min{bcost(2,2)+1, bcost(2,4)+11,
bcost(2,5)+8} = min{9+1, 3+11, 2+8} = 10
bcost(2,2) = min{bcost(1,1)+c(1,2)}
= min{bcost(1,1)+9} = 9
bcost(2,3) = min{bcost(1,1)+c(1,3)}
= min{bcost(1,1)+7} = 7
bcost(2,4) = min{bcost(1,1)+c(1,4)}
= min{bcost(1,1)+3} = 3
bcost(2,5) = min{bcost(1,1)+c(1,5)}
= min{bcost(1,1)+2} = 2
Now, d(5,12)=10
d(4,9)=6, d(4,10)=7, d(4,11)=8
d(3,6)=3, d(3,7)=2, d(3,8)=2
d(2,2)=1, d(2,3)=1, d(2,4)=1, d(2,5)=1

V4= d(5, V5)= d(5,12)= 10

V3= d(4, V4)= d(4,10) =7
V2 = d(3, V3) = d(3, 7) = 2
Therefore shortest path is 1-2-7-10-12
Minimum cost = 9+2+3+2= 16
ALL PAIRS SHORTEST PATHS
Let G=(V,E) be a directed graph with n vertices.
Let cost be a cost of adjacency matrix for G such that
cost(i, i) = 0 , 1<=i<=n
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.
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
Algorithm 5.3 Procedure to compute lengths of shortest paths
Last for loop is iterated n3 times time complexity is Ө(n3 )
For k=1,
i=1
A(1,1) = min(A[1,1], A[1,1]+A[1,1]) = min(0,0+0)= 0
A(1,2) = min(A[1,2], A[1,1]+A[1,2]) = min(4,0+4)= 4
A(1,3) = min(A[1,3], A[1,1]+A[1,3]) = min(11,0+11)= 11

i=2
A(2,1) = min(A[2,1], A[2,1]+A[1,1]) = min(6,6+0)= 6
A(2,2) = min(A[2,2], A[2,1]+A[1,2]) = min(0,6+4)= 0
A(2,3) = min(A[2,3], A[2,1]+A[1,3]) = min(2,6+11)= 2

i=3
A(3,1) = min(A[3,1], A[3,1]+A[1,1]) = min(3,3+0)= 3
A(3,2) = min(A[3,2], A[3,1]+A[1,2]) = min(∞,3+4)= 7
A(3,3) = min(A[3,3], A[3,1]+A[1,3]) = min(0,3+11)= 0

Therefore,
For k=2,
i=1
A(1,1) = min(A[1,1], A[1,2]+A[2,1]) = min(0,4+6)= 0
A(1,2) = min(A[1,2], A[1,2]+A[2,2]) = min(4,4+0)= 4
A(1,3) = min(A[1,3], A[1,2]+A[2,3]) = min(11,4+2)= 6

i=2
A(2,1) = min(A[2,1], A[2,2]+A[2,1]) = min(6,0+6)= 6
A(2,2) = min(A[2,2], A[2,2]+A[2,2]) = min(0,0+0)= 0
A(2,3) = min(A[2,3], A[2,2]+A[2,3]) = min(2,0+2)= 2

i=3
A(3,1) = min(A[3,1], A[3,2]+A[2,1]) = min(3, 7+6)= 3
A(3,2) = min(A[3,2], A[3,2]+A[2,2]) = min(7, 7+0)= 7
A(3,3) = min(A[3,3], A[3,2]+A[2,3]) = min(0, 7+2)= 0

Therefore,
For k=3,
i=1
A(1,1) = min(A[1,1], A[1,3]+A[3,1]) = min(0,6+3)= 0
A(1,2) = min(A[1,2], A[1,3]+A[3,2]) = min(4,6+7)= 4
A(1,3) = min(A[1,3], A[1,3]+A[3,3]) = min(6,6+0)= 6

i=2
A(2,1) = min(A[2,1], A[2,3]+A[3,1]) = min(6,2+3)= 5
A(2,2) = min(A[2,2], A[2,3]+A[3,2]) = min(0,2+7)= 0
A(2,3) = min(A[2,3], A[2,3]+A[3,3]) = min(2,2+0)= 2

i=3
A(3,1) = min(A[3,1], A[3,3]+A[3,1]) = min(3,0+3)= 3
A(3,2) = min(A[3,2], A[3,3]+A[3,2]) = min(7,3+7)= 7
A(3,3) = min(A[3,3], A[3,3]+A[3,3]) = min(0,3+0)= 0

Therefore,
SINGLE SOURCE SHORTEST PATH
Used mostly for negative cost.
Vertex 1 is source node
distk[1]=0 for all k=1…6

dist1[2]=6 dist1[3]=5 dist1[4]=5

dist1[5]=∞ dist1[6]= ∞ dist1[7]= ∞

dist2[2]= min{dist1[2], minidist1[i] + cost[i,2]} i=1,3,4,5,6,7

= min{6, 0+6, 5-2, 5+ ∞, ∞ + ∞, ∞ + ∞, ∞ + ∞} = 3
dist2[3]= min{dist1[3], minidist1[i] + cost[i,3]} i=1,2,4,5,6,7
= min{5, 0+5, 6+∞, 5-2, ∞ + ∞, ∞ + ∞, ∞ + ∞} = 3
dist2[4]= min{dist1[4], minidist1[i] + cost[i,4]} i=1,2,3,5,6,7
= min{5, 0+5, 6+∞, 5+∞, ∞ + ∞, ∞ + ∞, ∞ + ∞} = 5
dist2[5]= min{dist1[5], minidist1[i] + cost[i,5]} i=1,2,3,4,6,7
= min{∞, 0+ ∞, 6-1, 5+1, 5 + ∞, ∞ + ∞, ∞ + ∞} = 5
dist2[6]= min{dist1[6], minidist1[i] + cost[i,6]} i=1,2,3,4,5,7
= min{∞, 0+ ∞, 6+ ∞, 5+ ∞, 5 -1, ∞ + ∞, ∞ + ∞} = 4
dist2[7]= min{dist1[7], minidist1[i] + cost[i,7]} i=1,2,3,4,5,6
The second for loop takes O(n2) times if adjacency
matrices are used and O(e) if adjacency list are used
Overall time complexity
O(n3) – with adjacency matrices
O(ne) – with adjacency list.
0/1 knapsack
TRAVELLING SALESPERSON PROBLEM
The traveling salesman problem consists of a salesman and a set of
cities. The salesman has to visit each one of the cities starting from a
certain one (e.g. the hometown) and returning to the same city. The
challenge of the problem is that the traveling salesman wants to
minimize the total length of the trip.

Let G=(V,E) be a directed graph with edge costs cij.

Let |V| = n and assume n>1
A tour of G is a directed simple cycle that includes every vertex in V.
The cost of a tour is sum of the cost of edges on the tour.
The travelling salesperson problem is to find a tour of minimum cost.
Let g(i,S) be the length of a shortest path starting at vertex i, going
through all vertices in S and terminating at vertex 1.
g(1, V - { 1 }) is the length of an optimal salesperson tour.
Time complexity is ⍬(n22n)
In g(i,S) consider j with minimum value.
J(1,{2,3,4})=2 Optimal tour is
Thus tour starts from1 and goes to 2. 1,2,4,3,1
J(2,{3,4})=4
So next edge is 2 to 4
The remaining tour is for J(4, {3})
J(4,{3})=3