Algorithm Course Notes

Dynamic Programming 4

Dr. K V Arya
ABV- IIITM ,Gwalior
 Summary

Dynamic programming applied to

• All pairs shortest path problem ( Floyd’s
Algorithm )
• Transitive closure (Warshall’s Algorithm)
Constructing solutions using dynamic programming
• All pairs shortest path problem
• Matrix product.
 Graphs
A graph is an ordered pair G = ( V , E) where
V is a finite set of vertices
E  V * V is a set of edges
For example,
V = {1,2,3,4,5}
E={ (1,2) , (1,4) , (1,5) , (2,3) , (3,4) , (3,5) , (4,5) }
1

2 5

3 4
Directed Graphs

A directed graph is a graph with directions on the edges.

For example,
V = {1,2,3,4,5}
E ={ (1,2) , (1,4) , (1,5) , (2,3) , (3,4) , (3,5) , (4,5) }
1

2 5

3 4
Labeled , Directed Graphs
A labeled directed graph is a directed graph with positive costs
on the edges.
10 1 100

2 30 5

10 60
50

3 4
20

Applications : cities and distances by road.

Conventions: n is the number of vertices
e is the number of edges
 Paths in Graphs
A path in a graph G = ( V,E) is a sequence of edges
(v1, v2), (v2,v3) ,……,(vn,vn+1) є E
• The length of a path is the number of edges.
• The cost of a path is the sum of the cost of the edges.
For example , (1,2) , (2,3) ,(3,5) . Length 3 . Cost 70.
10 1 100
2 30 5

10
50 60
3 4
20
All pair shortest Paths
Given a labeled, directed graph G = (V,E) , find for each pair of
vertices v, w є V the cost of the shortest ( i.e. least cost ) path
from v to w.
Define Ak to be an n * n matrix with A k [i ,j] the cost of the
shortest path from i to j with internal vertices numbered ≤ k.
A 0 [i ,j] equals
• If i ≠j and (i,j) є E, then the cost of the edge from i to j.
• If i ≠j and (i,j) є E, then ∞
• If i=j , then 0.
Computing A k
Consider the shortest path from i to j with internal vertices
1….k. Either:
• It does not go through k, in which place it costs A k-1 [i,j].
• It goes through k, in which case it goes through k only
once, so it costs A k-1 [i,k] + A k-1 [k,j].
(only true for positive costs). Vertices numbered at most k-1

i
j

k
 Computing A k
Hence,
A k [i, j] = min {A k-1 [i , j] , A k- 1 [i , k] + A k- 1 [k , j]}

A k-1 j k Ak j

i i

All entries in A k depend upon row k and column k of A k-1

Computing A k
The entries in row k and column k of A k are the same as those in
A k-1.
Row k:
A k[ k ,j] := min {A k-1 [ k ,j] , A k-1 [ k ,k] + A k-1 [ k ,j] }
= min{A k-1 [ k ,j] ,0 + A k-1 [ k ,j] }
Column k:
A k [ i ,k] := min{A k-1 [ i ,k] , A k-1 [ i ,k] + A k-1 [ k ,k]}
= min{A k-1 [ i ,k], A k-1 [ i ,k] + 0}
= A k-1 [ i ,k]
Therefore, we can use the same array.
Floyd’s Algorithm
for i:=1 to n do
for j:=1 to n do
if (i, j) є E
then A[i ,j] := cost of (i, j)
else A[i ,j] := ∞
A[i ,j] := 0
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if A[i ,k ]+ a[k , j] < A[i ,j ] then
A[i , j] := A[ i , k] + A[ k , j] Running time: O(n3)
Example

1
10 100
30
2 5

50 10 60

3 4
20
Example
Storing the Shortest Path
for i:=1 to n do
for j:=1 to n do
P [ i, j ] := 0

if (i, j) є E
then A[i ,j] := cost of (i, j)
else A[i ,j] := ∞ Running time : O(n3)
A[i ,j] := 0 on termination P[i ,j] contains
for k:=1 to n do vertex on the shortest path from i to j
for i:=1 to n do
for j:=1 to n do
if A[i ,k ]+ A[k , j] < A[i ,j ] then
A[i , j] := A[ i , k] + A[ k , j]
P [ i, j ] := k
Computing the Shortest path
for i := 1 to n do
for j := 1 to n do
if A[ i, j] < ∞ then
print( i) ; shortest ( i ,j) ; print (j )
Procedure shortest ( I, j)
k: = P [ i, j]
if k > 0 then
shortest ( i , k); print ( k) ; shortest ( k , j)
Correctness of Shortest (i ,j)
Claim : Calling procedure shortest(i ,j) prints the internal nodes
on the shortest path from i to j.
Proof: A simple induction on the length of the path.
Warshall’s algorithm
Transitive Closure: given a directed graph G = (V ,E) , find for
each pair of vertices v, w є V whether there is a path from v to w.
Solution: make the cost of all edges 1, and run Floyd’s algorithm .
If on termination A[ i, j] ≠ ∞, then there is a path from i to j.

A cleaner solution : use Boolean values instead

 Warshall’s Algorithm
for i := 1 to n do
for j := 1 to n do
A[ i, j] := (i,j) є E
A[ i, i] := true
for k:= 1 to n do
for i:= 1 to n do
for j:= 1 to n do
A[ i, j] := A[ i, j] or (A[i, k] and A[ k, j])
 Finding Solutions using Dynamic
Programming
We have seen some examples of finding the cost of the
“best” solution to some interesting problems:
• Cheapest order of multiplying n rectangular matrices.
• Min cost binary search tree
• All pairs shortest path
We have also seen some examples of finding whether
solutions exist to some interesting problems:
• The knapsack problem
• Transitive closure
 Finding Solutions using Dynamic
Programming
What about actually finding the solutions?
We saw how to do it with the all pairs shortest path
problem.
The principle is the same every time:
• In the inner loop there is some kind of “decision” taken.
• Record the result of this decision in another table.
• Write a divide-and-conquer algorithm to construct the
solution from the information in the table.
Matrix Product

As another example , consider the matrix product

algorithm.
for i := 1 to n do m [ i,i ] := 0
for d := 1 to n-1 do
for i := 1 to n-d do
j := i + d
m [i , j] := min i≤ k < j ( m[ i, k] + m[k+1, j] + ri-1 r k r j )
 Matrix Product
In more detail:
for i := 1 to n do m [ i,i ] := 0
for d := 1 to n-1 do
for i := 1 to n-d do
j := i + d
m [i , j] := m [i , i] + m [i+1 , j] + ri-1 r i r j
for k := i +1 to j-1 do
if m [i , k] + m [k+1 , j] + ri-1 r k r j < m [i , j]
then
m [i , j] := m [i , k] + m [k+1 , j] + ri-1 r k r j
Matrix Product
Add the extra lines :
for i := 1 to n do m [ i,i ] := 0
for d := 1 to n-1 do
for i := 1 to n-d do
j := i + d
m [i , j] := m [i , i] + m [i+1 , j] + ri-1 r i r j
P [ i, j ] := i
for k := i +1 to j-1 do
if m [i , k] + m [k+1 , j] + ri-1 r k r j < m [i , j]
then
m [i , j] := m [i , k] + m [k+1 , j] + ri-1 r k r j

P [ i, j ] := k