DYNAMIC PROGRAMMING
Outlines
Introduction
Multistage Graphs
All-Pairs Shortest Paths
Single-Source Shortest Paths: General Weights
Optimal Binary Search Trees
Traveling Salesperson Problem
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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’.
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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.
Forward Method V1 V2
4
V3
6
V4 V5
Backward Method 2 2
5 4
9 1
4
7 3 2
7 t
s
3
11 5 5
2
11 6
Anupam Kumar Bairagi, PhD CSE, KU 8 [Link]
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 ].
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Maintain a cost matrix cost (n) which V1 V2 V3 V4 V5
stores the distance from any vertex to 4 6
the destination.
If a vertex is having more than one 2 2
5 4
path, then we have to choose the 9 1
minimum distance path and the 4
intermediate vertex, which gives the 7 3 2
minimum distance path, will be stored s 7 t
in the distance array ‘D’. 3
In this way we will find out the 11 5 5
minimum cost path from each and
2
every vertex. 11 6
Finally cost(1) will give the shortest
distance from source to destination. 8
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Backward Method
If there 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.
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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.
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Multistage Graphs (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
All-Pairs Shortest Paths [Floyd-Warshall]
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 in the adjacency matrix of G, L gives the length of each edge,
with L(i, i)=0 for i=1,2...n, L(i, j)>0 for all (i,j)∈ 𝐸, and L(i,j)=∞, 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.
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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.
𝐴𝑘 𝑖, 𝑗 = min{𝐴𝑘−1 𝑖, 𝑗 , 𝐴𝑘−1 𝑖, 𝑘 + 𝐴𝑘−1 𝑘, 𝑗 }}, 𝑘 ≥ 1
𝐴𝑘 (𝑖, 𝑗) – length of the shortest path from i to j
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)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
All-Pairs Shortest Paths (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
All-Pairs Shortest Paths (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
All-Pairs Shortest Paths (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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).
Anupam Kumar Bairagi, PhD CSE, KU [Link]
All-Pairs Shortest Paths (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Single-Source Shortest Paths: Bellman-Ford
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
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Single-Source Shortest Paths: General Weights
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Optimal Binary Search Tree
Binary Search Tree:
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Optimal Binary Search Tree
Our goal: With given keys with successful and
unsuccessful probabilities, we want to construct a BST
that will give us minimum cost.
However, try all of the BST is almost impossible !!
There is the dynamic programming, which will give us
the opportunity without making all the BST. That is
why, DP is a faster approach!!
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Optimal Binary Search Tree
We need: 𝐶 𝑖, 𝑗 = min 𝐶 𝑖, 𝑘 − 1 + 𝐶 𝑘, 𝑗 + 𝑊[𝑖, 𝑗]
𝑖<𝑘≤𝑗
We need: 𝑊 𝑖, 𝑗 = 𝑊 𝑖, 𝑗 − 1 + 𝑝𝑗 + 𝑞𝑗
We can construct a table with the help of these W and C
and then take the decision regarding OBST.
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Optimal Binary
Search Tree
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Optimal Binary
Search Tree
Anupam Kumar Bairagi, PhD CSE, KU [Link]
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.
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Travelling Salesperson Problem (Cont..)
The TSP has many practical applications
Manufacturing
Plane routing
Telephone routing
Networks
Traveling salespeople
Structure of crystals
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Travelling Salesperson Problem (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Travelling Salesperson Problem (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Travelling Salesperson Problem (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Travelling Salesperson Problem (Cont..)
Anupam Kumar Bairagi, PhD CSE, KU [Link]
TSP Example
Matrix C
Anupam Kumar Bairagi, PhD CSE, KU [Link]
TSP Example (Cont..)
Thus,
Now,
Anupam Kumar Bairagi, PhD CSE, KU [Link]
TSP Example (Cont..)
Finally,
Anupam Kumar Bairagi, PhD CSE, KU [Link]
Thanks for your Attention