DYNAMIC PROGRAMMING

Outlines

 Introduction
 Multistage Graphs
 All-Pairs Shortest Paths
 Single-Source Shortest Paths: General Weights
 Optimal Binary Search Trees
 Traveling Salesperson Problem
 Introduction
 Dynamic programming is an algorithm design method
that can be used when the solution of a problem can be
viewed as the result of a sequence of decisions
 Dynamic programming is typically applied to
optimization problems.
 Problems that can be solved by dynamic programming
satisfy the principle of optimality
 Important feature of the dynamic programming
approach is that optimal solutions to subproblems are
retained so as to avoid recomputing their values
 Dynamic programming is a bottom-up technique
 Multistage Graphs
 A multistage graph G = (V,E) is a directed graph in which the
vertices are portioned 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.
 If there will be only one vertex, then the sets V1 and Vk are
such that |V1|=|Vk| = 1.
 Let ‘s’ and ‘t’ be the source and destination respectively
 The cost of a path from source (s) to destination (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’.
 Multistage Graphs (Cont..)
 Each set Vi defines a stage in the graph.
 Every path from ‘s’ to ‘t’ starts in stage-1, goes to stage-2
then to stage-3, then to stage-4, and so on, and terminates in
stage-k.
 This MULISTAGE GRAPH problem can be solved in 2 ways.
V1 V2 V3 V4 V5
 Forward Method 4 6

 Backward Method 2 2
5 4
9 1
4
7 3 2
7 t
s
3
11 5 5
2
11 6

8
 Multistage Graphs (Cont..)
 Forward Method
 Assume that there are ‘k’ stages in a graph.
 In this FORWARD approach, we will find out the cost of each
and every node starting from the ‘k’ th stage to the 1st
stage.
 We will find out the path (i.e.) minimum cost path from
source to the destination (i.e,) [ Stage-1 to Stage-k ].
 Multistage Graphs (Cont..)
V1 V2 V3 V4 V5
 Maintain a cost matrix cost (n) which
stores the distance from any vertex to 4 6

the destination.
2 2
 If a vertex is having more than one 5 4
9 1
path, then we have to choose the 4
minimum distance path and the
7 3 2
intermediate vertex, which gives the 7 t
minimum distance path, will be stored s 3
in the distance array ‘D’.
11 5 5
 In this way we will find out the
minimum cost path from each and 2
11 6
every vertex.
 Finally cost(1) will give the shortest 8
distance from source to destination.
 Multistage Graphs (Cont..)
 For finding the path, start from vertex-1 then the distance
array D(1) will give the minimum cost neighbor vertex which
in turn give the next nearest vertex and proceed in this way
till we reach the Destination.
 For a ‘k’ stage graph, there will be ‘k’ vertex in the path.

Cost(12)=0 D(12)=0
Cost(11)=5 D(11)=12
Cost(10)=2 D(10)=12
Cost(9)=4 D(9)=12
Multistage Graphs (Cont..)
Multistage Graphs (Cont..)
Multistage Graphs (Cont..)
Multistage Graphs (Cont..)
Multistage Graphs (Cont..)
 Multistage Graphs (Cont..)
 Backward Method
 Ifthere are ‘k’ stages in a graph, using back ward approach we will find
out the cost of each & every vertex starting from 1st stage to the kth
stage.
 We will find out the minimum cost path from destination to source (i.e.,)
from stage k to stage 1.
 Process:
 It is similar to forward approach, but differs only in two or three ways.
 Maintain a cost matrix to store the cost of every vertices and a distance
matrix to store the minimum distance vertex.
 Find out the cost of each and every vertex starting from vertex 1 up to
vertex k.
 Multistage Graphs (Cont..)
 Process:
 To find out the path star from vertex ‘k’, then the distance array D (k)
will give the minimum cost neighbor vertex which in turn gives the next
nearest neighbor vertex and proceed till we reach the destination.
Multistage Graphs (Cont..)
Multistage Graphs (Cont..)
Multistage Graphs (Cont..)
Multistage Graphs (Cont..)
 All-Pairs Shortest Paths
 Let G=<V,E> be a directed graph ’V’ is a set of nodes and ‘E’ is the
set of edges.
 Each edge has an associated non-negative length.
 We want to calculate the length of the shortest path between each
pair of nodes
 Suppose the nodes of G are numbered from 1 to n, so
V={1,2,...N},and suppose G matrix L gives the length of each edge,
with L(i,j)=0 for i=1,2...n, L(i,j)>=for all i & j, and L(i,j)=infinity, if
the edge (i,j) does not exist.
 The principle of optimality applies: if k is the node on the shortest
path from i to j then the part of the path from i to k and the part
from k to j must also be optimal, that is shorter.
 All-Pairs Shortest Paths (Cont..)
 First, create a cost adjacency matrix for the given graph.
 Copy the above matrix-to-matrix D, which will give the direct distance between
nodes.
 We have to perform N iteration after iteration k. the matrix D will give you the
distance between nodes with only (1,2...,k) as intermediate nodes.
 At the iteration k, we have to check for each pair of nodes (i,j) whether or not
there exists a path from i to j passing through node k.
𝑨𝒌(𝒊, 𝒋) = 𝒎𝒊𝒏{𝒌−(𝒊, 𝒋), 𝑨𝒌−(𝒊, 𝒌) + 𝑨𝒌−(𝒌 − 𝟏, 𝒋)} k≥1
𝑨𝒌(𝒊, 𝒋) − 𝑳𝒆𝒏𝒈𝒕𝒉 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒉𝒐𝒓𝒕𝒆𝒔𝒕 𝒑𝒂𝒕𝒉 𝒇𝒓𝒐𝒎 𝒊 𝒕𝒐 𝒋.
 Let G=(V,E) is a directed graph with ‘N’ Vertices. Let cost be the cost of the
adjacency matrix for G such that cost(i,i)=0 (1≤i≤n) then cost(i,j) is the length or
cost of the edge <i,j>. If <i,j> exists the edge belongs to E(G) and cost(i,j)=α, if
i≠j and <i,j> ∉ E(G)
All-Pairs Shortest Paths (Cont..)
All-Pairs Shortest Paths (Cont..)
All-Pairs Shortest Paths (Cont..)
 All-Pairs Shortest Paths (Cont..)
 At 1st iteration we have to check the each pair(i,j) whether
there is a path through node 1.
 If so we have to check whether it is minimum than the
previous value and if i is so than the distance through 1 is the
value of d1(i,j).
 At the same time we have to solve the intermediate node in
the matrix position p(i,j).
All-Pairs Shortest Paths (Cont..)
 Single-Source Shortest Paths: General Weights
 The recurrence relation for distance is as follows:

 This recurrence can be used to compute distk from

distk-1, for k=2,3,…,n-1
 Single-Source Shortest Paths: General Weights
 distk[1]=0 for all k as this is
source node
 dist1[2]=6, dist1[3]=5, dist1[4]=5
 The distance dist1[5/6/7] is inf
as there are no edges to these
from 1
Single-Source Shortest Paths: General Weights
 Travelling Salesperson Problem
 Given a complete, weighted graph on n nodes, find the
least weight Hamiltonian cycle, a cycle that visits
every node once.

 Though this problem is easy enough to explain, it is

very difficult to solve.

 Finding all the Hamiltonian cycles of a graph takes

exponential time. Therefore, TSP is in the class NP.
 Travelling Salesperson Problem (Cont..)
 The TSP has many practical applications
 Manufacturing

 Plane routing
 Telephone routing
 Networks

 Traveling salespeople
 Structure of crystals
 Travelling Salesperson Problem (Cont..)

 Travelling Salesperson Problem (Cont..)

 Travelling Salesperson Problem (Cont..)

 Travelling Salesperson Problem (Cont..)

TSP Example

Matrix C
 TSP Example (Cont..)
 Thus,

 Now,
 TSP Example (Cont..)

 Finally,
Thanks for your Attention

Q&A