Subject: Design and Analysis of

Algorithms
Module Number: 4

Module Name: Dynamic Programming

SME NAME: [Link]
AP/CSSP
1
Introduction to DAA

Syllabus
General method, Multistage Graphs, Single source shortest paths: Dijkstra's Algorithm, All Pairs
Shortest Paths: Floyd's Algorithm, Optimal Binary Search Trees, Knapsack problem, Bellman-
Ford Algorithm, Travelling Sales Person problem.

2
Introduction to DAA

Dynamic Programming
• Dynamic programming is a technique for solving problems with overlapping subproblems.
• subproblems arise from a recurrence relating a given problem’s solution to solutions of its smaller
subproblems.
• DP suggests solving each of the smaller subproblems only once and recording the results in a table from
which a solution to the original problem can then be obtained.
• The Dynamic programming can be used when the solution to a problem can be viewed as the result of
sequence of decisions.
• Limitations
• The method is applicable to only those problems which possess the property of principle of optimality.
• We must keep track of partial solutions.
• Dynamic programming is more complex and time-consuming 3
Introduction to DAA

Dynamic Programming
• Characteristics of Dynamic Programming
• Characterize structure of optimal solution, i.e. build a mathematical model of the solution.
• Recursively define the value of the optimal solution.
• Using bottom up approach, compute the value of the optimal solution for each possible sub problems.
• Construct optimal solution for the original problem using information computed in the previous step.
• Applications of Dynamic Programming
• Knapsack problem
• Optimal binary search tree
• Travelling salesman problem
• All pair shortest path problem
• Assembly line scheduling and Multi stage graph problem 4
Introduction to DAA

Dynamic Programming
• Principle of Optimality
• The principle of optimality is the heart of dynamic programming. It states that to find the optimal solution
of the original problem, a solution of each sub problem also must be optimal. It is not possible to derive
optimal solution using dynamic programming if the problem does not possess the principle of optimality.
• Shortest path problem satisfies the principle of optimality. If A – X1 – X2 – . . . Xn – B is the shortest path
between nodes A and B, then any sub path Xi to Xj must be shortest. If there exist multiple paths from Xi to
Xj, and the selected path is not minimum, then obviously the path from A to B cannot be shortest.

5
Introduction to DAA

Dynamic Programming
• Elements of Dynamic Programming
• Optimal substructure: “For the optimal solution of the problem, a solution of sub problem also must be
optimal”. Dynamic programming builds the optimal solution of the bigger problem using the solution of
smaller sub problems. Hence we should consider only those sub problems which have an optimal solution.
• Overlapping subproblems: When the big problem is divided into small problems, it may create exponential
subproblems. Only polynomial numbers of them are distinct.
• Following figure shows the overlapping problems
of the binomial coefficient. Dynamic programming
saves solution in the table, so no rework is done.
When C(n – 3, r – 2) problem encounters again,
its solution is retrieved from the table. 6
Introduction to DAA

Dynamic Programming -Multistage Graph

• Multistage Graph problem is defined as follow:
• Multistage graph G = (V, E, W) is a weighted directed graph in which vertices are partitioned into k ≥ 2
disjoint sub sets V = {V1, V2, …, Vk} such that if edge (u, v) is present in E then u ∈ Vi and v ∈ Vi+1, 1 ≤
i ≤ k. The goal of multistage graph problem is to find minimum cost path from source to destination vertex.
• The input to the algorithm is a k-stage graph, n vertices are indexed in increasing order of stages.
• The algorithm operates in the backward direction, i.e. it starts from the last vertex of the graph and proceeds
in a backward direction to find minimum cost path.
• Minimum cost of vertex j ∈ Vi from vertex r ∈ Vi+1 is defined as,
Cost[j] = min{ c[j, r] + cost[r] }
• where, c[j, r] is the weight of edge <j, r> and cost[r] is the cost of moving from end vertex to vertex r.

7
Introduction to DAA

Dynamic Programming -Multistage Graph

• Let G=(v,E) be a directed graph. In this we divide the problem into no. of stages or multiple stages then we
try to solve whole problem.
• Multistage graph problem is to determine shortest path from source to destination. This can be solved by
using either forward or backward approach.
• In forward approach we will find the path from destination to source, in backward approach we will find the
path from source to destination.

8
Introduction to DAA

Dynamic Programming -Multistage Graph using forward approach

Cost of node j at
stage i to reach
terminal node t

Stage number
Node 9
Introduction to DAA

Dynamic Programming -Multistage Graph using forward approach

cost(5,12)=0
cost(4,9)=c(9,12) = 4
cost(4,10)=c(10,12)=2

cost(4,11)=c(11,12)=5

10
 Introduction to DAA

Dynamic Programming -Multistage Graph

• Algorithm: forward approach

11
 Introduction to DAA

Dynamic Programming -Multistage Graph

• Algorithm: forward approach

12
Introduction to DAA

Dynamic Programming -Multistage Graph using Backward Approach

13
Introduction to DAA

Dynamic Programming -Multistage Graph using Backward Approach

bcost(2,2) = 9
bcost(2,3)=7
bcost(2,4)=3
bcost(2,5)=2

14
 Introduction to DAA

Dynamic Programming -Multistage Graph

• Algorithm: Backward Approach

15
Introduction to DAA

Dynamic Programming -Multistage Graph using forward approach and Backward

approach
Problem 1:

Problem 2:

16
Dynamic Programming

Single source shortest paths: Dijkstra's Algorithm

• Single-source shortest-paths problem is defined as follows. For a given vertex called

the source in a weighted connected graph, the problem is to find shortest paths to all its
other vertices.
• The single-source shortest-paths problem asks for a family of paths, each leading from
the source to a different vertex in the graph, though some paths may, of course, have
edges in common.

17
Dynamic Programming

3.1. Dijkstra's Algorithm

• Dijkstra's Algorithm is the best-known algorithm for the single-source shortest-paths

problem. This algorithm is applicable to undirected and directed graphs with
nonnegative weights only.
• Working - Dijkstra's algorithm finds the shortest paths to a graph's vertices in order of
their distance from a given source.

18
Dynamic Programming

3.1. Dijkstra's Algorithm

• First, it finds the shortest path from the source to a vertex nearest to it, then to a second
nearest, and so on.
• In general, before its ith iteration commences, the algorithm has already identified the
shortest paths to i-1 other vertices nearest to the source. These vertices, the source, and
the edges of the shortest paths leading to them from the source form a subtree Ti of the
given graph shown in the figure.
• Since all the edge weights are nonnegative, the next vertex nearest to the source can be
found among the vertices adjacent to the vertices of Ti.
19
Dynamic Programming

3.1. Dijkstra's Algorithm

• The set of vertices adjacent to the vertices in Ti can be referred to as "fringe vertices";
they are the candidates from which Dijkstra's algorithm selects the next vertex nearest
to the source.
• To identify the ith nearest vertex, the algorithm computes, for every fringe vertex u,
the sum of the distance to the nearest tree vertex v (given by the weight of the edge (v,
u)) and the length d., of the shortest path from the source to v (previously determined
by the algorithm) and then selects the vertex with the smallest such sum. The fact that it
suffices to compare the lengths of such special paths is the central insight of Dijkstra's
20
algorithm.
Dynamic Programming

3.1. Dijkstra's Algorithm

• To facilitate the algorithm's operations, we label each vertex with two labels.
• The numeric label d indicates the length of the shortest path from the source to
this vertex found by the algorithm so far; when a vertex is added to the tree, d
indicates the length of the shortest path from the source to that vertex.
• The other label indicates the name of the next-to-last vertex on such a path, i.e.,
the parent of the vertex in the tree being constructed. (It can be left unspecified
for the sources and vertices that are adjacent to none of the current tree vertices.)
With such labeling, finding the next nearest vertex u* becomes a simple task of finding a
21
fringe vertex with the smallest d value. Ties can be broken arbitrarily.
Dynamic Programming

3.1. Dijkstra's Algorithm

• After we have identified a vertex u* to be added to the tree, we need to perform two
operations:
• Move u* from the fringe to the set of tree vertices.
• For each remaining fringe vertex u that is connected to u* by an edge of weight
w(u*, u) such that du*+ w(u*, u) <du, update the labels of u by u* and du*+ w(u*,
u), respectively

22
Dynamic Programming

3.1. Dijkstra's Algorithm

Illustration: An example of Dijkstra's

algorithm is shown here

The shortest paths (identified by following nonnumeric labels backward from a

destination vertex in the left column to the source) and their lengths (given by numeric
labels of the tree vertices) are as follows:

23
Dynamic Programming

3.1. Dijkstra's Algorithm

24
Dynamic Programming

3.1. Dijkstra's Algorithm

The pseudocode of Dijkstra’s algorithm is given below. Note that in the following pseudocode,
VT contains a given source vertex and the fringe contains the vertices adjacent to it after
iteration 0 is completed

25
Dynamic Programming

Dijkstra's Algorithm

26
Dynamic Programming

Algorithm Analysis

• The time efficiency of Dijkstra’s algorithm depends on the data structures used for
implementing the priority queue and for representing an input graph itself
• Efficiency is Θ(|V|2) for graphs represented by their weight matrix and the priority queue
implemented as an unordered array.
• For graphs represented by their adjacency lists and the priority queue implemented as a
min- heap, it is in O (|E| log |V| )

27
Dynamic Programming

Applications

• Transportation planning and packet routing in communication networks, including the

Internet
• Finding shortest paths in social networks, speech recognition, document formatting,
robotics, compilers, and airline crew scheduling.

28