Department of AIML & CSM

DESIGN AND ANALYSIS OF ALGORITHMS

STUDY MATERIAL
Module 3
B.Tech II Year – IISem

PREPARED & COMPILED BY

Mrs. S.Asha Jyothi

Assistant Professor,
Department of AI&ML
JBIET
Bhaskar Nagar, Yenkapally (V), Moinabad (M),
Ranga Reddy,District Hyderabad., Moinabad,
Hyderabad 500075Telangana,
India.
 MODULE 3
Dynamic Programming

General Method, Principle of Optimality, Applications: Multistage Graphs, Matrix Chain Multiplication,
Optimal Binary Search Trees, 0/1 Knapsack Problem, All Pairs Shortest Path Problem, Travelling Sales
Person Problem, Reliability Design.

Dynamic Programming

Dynamic programming is a technique that breaks the problems into sub-problems, and saves the result for
future purposes so that we do not need to compute the result again. The subproblems are optimized to
optimize the overall solution is known as optimal substructure property. The main use of dynamic
programming is to solve optimization problems. Here, optimization problems mean that when we are trying
to find out the minimum or the maximum solution of a problem. The dynamic programming guarantees to
find the optimal solution of a problem if the solution exists.

The definition of dynamic programming says that it is a technique for solving a complex problem by first
breaking into a collection of simpler subproblems, solving each subproblem just once, and then storing their
solutions to avoid repetitive computations.

How does the dynamic programming approach work?

The following are the steps that the dynamic programming follows:

o It breaks down the complex problem into simpler subproblems.

o It finds the optimal solution to these sub-problems.
o It stores the results of subproblems (memoization). The process of storing the results of
subproblems is known as memorization.
o It reuses them so that same sub-problem is calculated more than once.
o Finally, calculate the result of the complex problem.

The above five steps are the basic steps for dynamic programming. The dynamic programming is
applicable that are having properties such as:

Those problems that are having overlapping subproblems and optimal substructures. Here, optimal
substructure means that the solution of optimization problems can be obtained by simply combining the
optimal solution of all the subproblems.

In the case of dynamic programming, the space complexity would be increased as we are storing the
intermediate results, but the time complexity would be decreased.

Approaches of dynamic programming

There are two approaches to dynamic programming:

 o Top-down approach
o Bottom-up approach

Top-down approach

The top-down approach follows the memorization technique, while bottom-up approach follows the
tabulation method. Here memorization is equal to the sum of recursion and caching. Recursion means
calling the function itself, while caching means storing the intermediate results.

Advantages

o It is very easy to understand and implement.

o It solves the subproblems only when it is required.
o It is easy to debug.

Disadvantages

It uses the recursion technique that occupies more memory in the call stack. Sometimes when the recursion
is too deep, the stack overflow condition will occur.

It occupies more memory that degrades the overall performance.

Let's understand dynamic programming through an example.

int fib(int n)
{
if(n<0)
error;
if(n==0)
return 0;
if(n==1)
return 1;
sum = fib(n-1) + fib(n-2);
}

In the above code, we have used the recursive approach to find out the Fibonacci series. When the value of
'n' increases, the function calls will also increase, and computations will also increase. In this case, the time
complexity increases exponentially, and it becomes 2n.

One solution to this problem is to use the dynamic programming approach. Rather than generating the
recursive tree again and again, we can reuse the previously calculated value. If we use the dynamic
programming approach, then the time complexity would be O(n).

When we apply the dynamic programming approach in the implementation of the Fibonacci series, then
the code would look like:
static int count = 0;
int fib(int n)
{
if(memo[n]!= NULL)
return memo[n];
count++;
if(n<0)
error;
if(n==0)
return 0;

if(n==1)
return 1;
sum = fib(n-1) + fib(n-2);
memo[n] = sum;
}

In the above code, we have used the memorization technique in which we store the results in an array to
reuse the values. This is also known as a top-down approach in which we move from the top and break the
problem into sub-problems.

Bottom-Up approach

The bottom-up approach is also one of the techniques which can be used to implement the dynamic
programming. It uses the tabulation technique to implement the dynamic programming approach. It solves
the same kind of problems but it removes the recursion. If we remove the recursion, there is no stack
overflow issue and no overhead of the recursive functions. In this tabulation technique, we solve the
problems and store the results in a matrix.

There are two ways of applying dynamic programming:

o Top-Down
o Bottom-Up

The bottom-up is the approach used to avoid the recursion, thus saving the memory space. The bottom-up
is an algorithm that starts from the beginning, whereas the recursive algorithm starts from the end and works
backward. In the bottom-up approach, we start from the base case to find the answer for the end. As we
know, the base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts from the base
cases, so we will start from 0 and 1.

Key points

o We solve all the smaller sub-problems that will be needed to solve the larger sub-problems then
move to the larger problems using smaller sub-problems.
o We use for loop to iterate over the sub-problems.
o The bottom-up approach is also known as the tabulation or table filling method.
Let's understand through an example.

REFER NOTEBOOK

The code for implementing the Fibonacci series using the bottom-up approach is given below:

int fib(int n)
{
int A[];
A[0] = 0, A[1] = 1;
for( i=2; i<=n; i++)
{
A[i] = A[i-1] + A[i-2]
}
return A[n];
}

In the above code, base cases are 0 and 1 and then we have used for loop to find other values of Fibonacci
series.

Fibonacci sequence

Fibonacci sequence is the sequence of numbers in which every next item is the total of the previous two
items. And each number of the Fibonacci sequence is called Fibonacci number.

Example: 0 ,1,1,2,3,5,8,13,21, ........................ is a Fibonacci sequence.

The Fibonacci numbers F_nare defined as follows:

F0 = 0
Fn=1
Fn=F(n-1)+ F(n-2)
FIB (n)
1. If (n < 2)
2. then return n
3. else return FIB (n - 1) + FIB (n - 2)

Figure: shows four levels of recursion for the call fib (8):
 Figure: Recursive calls during computation of Fibonacci number

A single recursive call to fib (n) results in one recursive call to fib (n - 1), two recursive calls to fib (n - 2),
three recursive calls to fib (n - 3), five recursive calls to fib (n - 4) and, in general, Fk-1 recursive calls to
fib (n - k) We can avoid this unneeded repetition by writing down the conclusion of recursive calls and
looking them up again if we need them later. This process is called memorization.

Here is the algorithm with memorization

MEMOFIB (n)
1 if (n < 2)
2 then return n
3 if (F[n] is undefined)
4 then F[n] ← MEMOFIB (n - 1) + MEMOFIB (n - 2)
5 return F[n]

If we trace through the recursive calls to MEMOFIB, we find that array F [] gets filled from bottom up. I.e.,
first F [2], then F [3], and so on, up to F[n]. We can replace recursion with a simple for-loop that just fills
up the array F [] in that order

ITERFIB (n)
1 F [0] ← 0
2 F [1] ← 1
3 for i ← 2 to n
4 do
5 F[i] ← F [i - 1] + F [i - 2]
6 return F[n]

This algorithm clearly takes only O (n) time to compute Fn.

Multistage Graph Problem

A multistage graph is a directed and weighted graph, in which all vertices are divided into stages, such
that all the edges are only directed from the vertex of the current stage to the vertex of the next stage (i.e
there is no edge between the vertex of the same stage and to the previous stage vertex). Both the first
and last stage contains only one vertex called source and destination/sink respectively.

Mathematically, a multistage graph can be defined as:

Multistage graph G = (V, E, W) is a weighted directed graph in which vertices are partitioned into k ≥ 2
disjoint subsets 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 sets V1 and Vk are such that |V1 | = |Vk|=1

A multistage graph with 9 vertices and 5 stages

In the multistage graph problem, we are required to find the shortest path between the source and the
sink/destination. This problem can be easily solved by dynamic programming. Before getting started,
let’s understand what is Dynamic Programming(DP).

Dynamic Programming:

Dynamic Programming is an optimization over recursion. Whenever we have an optimization problem

with repeated subproblems we use dynamic programming because, in dynamic programming, we store
the solution to smaller subproblems in a table, and use it when the same subproblem arrives. Dynamic
programming reduces the exponential time complexity of a recursive algorithm to polynomial time
complexity. Dynamic programming can be applied to many problems like travelling salesman problems
and multistage graph problems.

The multistage graph problem can be solved in two ways using dynamic programming :
1. Forward approach

2. Backward approach

In the forward approach, we assume that there are k stages in the graph. We start from the last stage and
find out the cost of each and every node to the first stage. We then find out the minimum cost path from
the source to destination (i.e from stage 1 to stage k).

Procedure:

1. Maintain a cost array cost[n] which stores the distance from any vertex to the destination.

2. If a vertex has more than one path, then the path with the minimum distance is chosen and the
intermediate vertex is stored in the distance array D[n]. This will give us a minimum cost path from
each and every vertex.

3. Finally, the cost from 1st vertex cost(1,k) gives the minimum cost of the shortest path from source to
destination.

4. For finding the path, start from vertex-1 then the distance array D(1) will give the minimum cost
neighbour vertex which in turn gives 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.

5. For forward approach,

Cost (i,j) = min {C (j,l) + Cost (i+1,l) } l∈Vi + 1 & (j,l)∈E

Algorithm:

MULTI_STAGE(G, k, n, p)

// Input:

k: Number of stages in graph G = (V, E)

c[i, j]:Cost of edge (i, j)

// Output: p[1:k]:Minimum cost path

cost[n] ← 0

for j ← n — 1 to 1 do

//Let r be a vertex such that (j, r) E and c[j, r] + cost[r] is minimum

cost[j] ← c[j, r] + cost[r]

π[j] ← r

end

//Find minimum cost path

p[1] ← 1

p[k] ← n

for j ← 2 to k — 1 do

p[j] ← π[p[j — 1]]

end

Example: Find minimum path cost between vertex s and t for following multistage graph using
dynamic programming.
Solution:

In the above graph, cost of an edge is represented as c(i, j). We need to find the minimum cost path from
vertex 1 to vertex 12. Using the below formula we can find the shortest cost path from source to
destination:

cost(i,j)=min{c(j,l)+cost(i+1,l)}

Step 1:

Stage 5

cost(5,12)=c(12,12)=0

We use forward approach here therefore (cost(5,12) = 0 ). Here, 5 represents the stage number and 12
represents a node in that stage. Since there are no outgoing edges from vertex 12, the cost is 0 and
D[12]=12

Step 2:

Stage 4

cost(4,9)= c(9,12) = 4 D[9]=12

cost(4,10) = c(10,12) = 2 D[10]=12

cost(4,11) = c(11,12) = 5 D[11]=12

Step 3:

Stage 3

cost(3,6)=min{c(6,9)+cost(4,9), c(6,10)+cost(4,10)}

= min{6+4,5+2} =min{10,7}=7 D[6]=10

cost(3,7)=min{c(7,9)+cost(4,9), c(7,10)+cost(4,10)}
= min{4+4,3+2} =min{8,5}=5 D[7]=10

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

= min{5+2,6+5} =min{7,11}=7 D[7]=10

Step 4:

Stage 2

cost(2,2) = min{c(2,6)+cost(3,6), c(2,7)+cost(3,7), c(2,8)+cost(3,8)}

= min{4+7,2+5,1+7}=min{11,7,8}=7 D[2]=7

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

= min{2+7,7+5}=min{9,12}=9 D[3]=6

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

= min{11+7}=min{18}=18 D[4]=8

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

= min{11+5,8+7}=min{16,15}=15 D[3]=8

Step 5:

Stage 1

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+7, 7+9, 3+18, 2+15}=min{16,16,21,17}=16

D[1] = 2 (we can take 3 also )

The path through which we have to find the shortest distance

 Start from vertex — 2

D ( 1) = 2

D ( 2) = 7

D ( 7) = 10

D (10) = 12

So, the minimum –cost path is,

The cost is 9+2+3+2=16

Code for this is given above.

ANALYSIS: The time complexity of this forward method is 𝑂(|𝑉| + |𝐸|)

2. BACKWARD METHOD :

If there are ‘K’ stages in a graph using backward 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

PROCEDURE:

1. It is similar to the forward approach but differs only in two or three ways.

2. Maintain a cost matrix to store the cost of every vertex and a distance matrix to store the minimum
distance vertex.

3. Find out the cost of each and every vertex starting from vertex 1 up to vertex k.
 4. To find out the path star from vertex ‘k’, then the distance array D (k) will give the minimum cost
neighbour vertex which in turn gives the next nearest neighbour vertex and proceed till we reach the
destination.

Application of multistage graph :

1. It is used to find the minimum cost shortest path.

If a problem can be represented as a multistage graph then it can be solved by dynamic programming.

Matrix Chain Multiplication

Example: We are given the sequence {4, 10, 3, 12, 20, and 7}. The matrices have size 4 x 10, 10 x 3, 3 x
12, 12 x 20, 20 x 7. We need to compute M [i,j], 0 ≤ i, j≤ 5. We know M [i, i] = 0 for all i.

Let us proceed with working away from the diagonal. We compute the optimal solution for the product of
2 matrices.

Here P0 to P5 are Position and M1 to M5 are matrix of size (pi to pi-1)

On the basis of sequence, we make a formula

In Dynamic Programming, initialization of every method done by '0'.So we initialize it by '0'.It will sort
out diagonally.
We have to sort out all the combination but the minimum output combination is taken into consideration.
Calculation of Product of 2 matrices:
1. m (1,2) = m1 x m2
= 4 x 10 x 10 x 3
= 4 x 10 x 3 = 120

2. m (2, 3) = m2 x m3
= 10 x 3 x 3 x 12
= 10 x 3 x 12 = 360

3. m (3, 4) = m3 x m4
= 3 x 12 x 12 x 20
= 3 x 12 x 20 = 720

4. m (4,5) = m4 x m5
= 12 x 20 x 20 x 7
= 12 x 20 x 7 = 1680

o We initialize the diagonal element with equal i,j value with '0'.
o After that second diagonal is sorted out and we get all the values corresponded to it
Now the third diagonal will be solved out in the same way.
Now product of 3 matrices:
M [1, 3] = M1 M2 M3
1. There are two cases by which we can solve this multiplication: ( M1 x M2 ) + M3, M1+ (M2 x M3)
2. After solving both cases we choose the case in which minimum output is there.

M [1, 3] =264
As Comparing both output 264 is minimum in both cases so we insert 264 in table and ( M1 x M2) +
M3 this combination is chosen for the output making.
M [2, 4] = M2 M3 M4
1. There are two cases by which we can solve this multiplication: (M2 x M3)+M4, M2+(M3 x M4)
2. After solving both cases we choose the case in which minimum output is there.
M [2, 4] = 1320
As Comparing both output 1320 is minimum in both cases so we insert 1320 in table and M2+(M3 x M4)
this combination is chosen for the output making.
M [3, 5] = M3 M4 M5
1. There are two cases by which we can solve this multiplication: ( M3 x M4) + M5, M3+ ( M4xM5)
2. After solving both cases we choose the case in which minimum output is there.

M [3, 5] = 1140
As Comparing both output 1140 is minimum in both cases so we insert 1140 in table and ( M3 x M4) +
M5this combination is chosen for the output making.

Now Product of 4 matrices:

M [1, 4] = M1 M2 M3 M4
There are three cases by which we can solve this multiplication:
1. ( M1 x M2 x M3) M4
2. M1 x(M2 x M3 x M4)
3. (M1 xM2) x ( M3 x M4)
After solving these cases we choose the case in which minimum output is there

M [1, 4] =1080

As comparing the output of different cases then '1080' is minimum output, so we insert 1080 in the table
and (M1 xM2) x (M3 x M4) combination is taken out in output making,

M [2, 5] = M2 M3 M4 M5

There are three cases by which we can solve this multiplication:

1. (M2 x M3 x M4)x M5
2. M2 x( M3 x M4 x M5)
3. (M2 x M3)x ( M4 x M5)

After solving these cases we choose the case in which minimum output is there
 M [2, 5] = 1350

As comparing the output of different cases then '1350' is minimum output, so we insert 1350 in the table
and M2 x( M3 x M4 xM5)combination is taken out in output making.

Now Product of 5 matrices:

M [1, 5] = M1 M2 M3 M4 M5

There are five cases by which we can solve this multiplication:

1. (M1 x M2 xM3 x M4 )x M5
2. M1 x( M2 xM3 x M4 xM5)
3. (M1 x M2 xM3)x M4 xM5
4. M1 x M2 x(M3 x M4 xM5)

After solving these cases we choose the case in which minimum output is there

M [1, 5] = 1344

As comparing the output of different cases then '1344' is minimum output, so we insert 1344 in the table
and M1 x M2 x(M3 x M4 x M5)combination is taken out in output making.

Final Output is:

Step 3: Computing Optimal Costs: let us assume that matrix Ai has dimension pi-1 x pi for i=1, 2, 3. n.
The input is a sequence (p0 ,p1 ,......pn) where length [p] = n+1. The procedure uses an auxiliary table m
[1....n, 1.....n] for storing m [i, j] costs an auxiliary table s [1.....n, 1.....n] that record which index of k
achieved the optimal costs in computing m [i, j].

The algorithm first computes m [i, j] ← 0 for i=1, 2, 3 n, the minimum costs for the chain of length 1.

Algorithm of Matrix Chain Multiplication

MATRIX-CHAIN-ORDER (p)

1. n length[p]-1

2. for i ← 1 to n

3. do m [i, i] ← 0

4. for l ← 2 to n // l is the chain length

5. do for i ← 1 to n-l + 1

6. do j ← i+ l -1

7. m[i,j] ← ∞

8. for k ← i to j-1

9. do q ← m [i, k] + m [k + 1, j] + pi-1 pk pj

10. If q < m [i,j]

11. then m [i,j] ← q

12. s [i,j] ← k

13. return m and s.

We will use table s to construct an optimal solution.

Step 1: Constructing an Optimal Solution:

PRINT-OPTIMAL-PARENS (s, i, j)

1. if i=j

2. then print "A"

3. else print "("

4. PRINT-OPTIMAL-PARENS (s, i, s [i, j])

5. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j)

6. print ")"

Analysis: There are three nested loops. Each loop executes a maximum n times.

1. l, length, O (n) iterations.

2. i, start, O (n) iterations.
3. k, split point, O (n) iterations

Body of loop constant complexity

Total Complexity is: O (n3)

Optimal Binary Search Tree

As we know that in binary search tree, the nodes in the left subtree have lesser value than the root
node and the nodes in the right subtree have greater value than the root node.

We know the key values of each node in the tree, and we also know the frequencies of each node
in terms of searching means how much time is required to search a node. The frequency and key-
value determine the overall cost of searching a node. The cost of searching is a very important
factor in various applications. The overall cost of searching a node should be less. The time
required to search a node in BST is more than the balanced binary search tree as a balanced
binary search tree contains a lesser number of levels than the BST. There is one way that can
reduce the cost of a binary search tree is known as an optimal binary search tree.

Let's understand through an example.

If the keys are 10, 20, 30, 40, 50, 60, 70

In the above tree, all the nodes on the left subtree are smaller than the value of the root node,
and all the nodes on the right subtree are larger than the value of the root node. The maximum
time required to search a node is equal to the minimum height of the tree, equal to logn.

Now we will see how many binary search trees can be made from the given number of keys.

For example: 10, 20, 30 are the keys, and the following are the binary search trees that can be
made out from these keys.

The Formula for calculating the number of trees:

When we use the above formula, then it is found that total 5 number of trees can be created.

The cost required for searching an element depends on the comparisons to be made to search
an element. Now, we will calculate the average cost of time of the above binary search trees.
In the above tree, total number of 3 comparisons can be made. The average number of
comparisons can be made as:

In the above tree, the average number of comparisons that can be made as:
In the above tree, the average number of comparisons that can be made as:

In the above tree, the total number of comparisons can be made as 3. Therefore, the average
number of comparisons that can be made as:
In the above tree, the total number of comparisons can be made as 3. Therefore, the average
number of comparisons that can be made as:

In the third case, the number of comparisons is less because the height of the tree is less, so it's
a balanced binary search tree.

Till now, we read about the height-balanced binary search tree. To find the optimal binary
search tree, we will determine the frequency of searching a key.

Let's assume that frequencies associated with the keys 10, 20, 30 are 3, 2, 5.

The above trees have different frequencies. The tree with the lowest frequency would be
considered the optimal binary search tree. The tree with the frequency 17 is the lowest, so it would
be considered as the optimal binary search tree.

Dynamic Approach

Consider the below table, which contains the keys and frequencies.
First, we will calculate the values where j-i is equal to zero.

When i=0, j=0, then j-i = 0

When i = 1, j=1, then j-i = 0

When i = 2, j=2, then j-i = 0

When i = 3, j=3, then j-i = 0

When i = 4, j=4, then j-i = 0

Therefore, c[0, 0] = 0, c[1 , 1] = 0, c[2,2] = 0, c[3,3] = 0, c[4,4] = 0

Now we will calculate the values where j-i equal to 1.

When j=1, i=0 then j-i = 1

When j=2, i=1 then j-i = 1

When j=3, i=2 then j-i = 1

When j=4, i=3 then j-i = 1

Now to calculate the cost, we will consider only the jth value.

The cost of c[0,1] is 4 (The key is 10, and the cost corresponding to key 10 is 4).

The cost of c[1,2] is 2 (The key is 20, and the cost corresponding to key 20 is 2).

The cost of c[2,3] is 6 (The key is 30, and the cost corresponding to key 30 is 6)

The cost of c[3,4] is 3 (The key is 40, and the cost corresponding to key 40 is 3)

Now we will calculate the values where j-i = 2

When j=2, i=0 then j-i = 2

When j=3, i=1 then j-i = 2

When j=4, i=2 then j-i = 2

In this case, we will consider two keys.

o When i=0 and j=2, then keys 10 and 20. There are two possible trees that can be made out from
these two keys shown below:
In the first binary tree, cost would be: 4*1 + 2*2 = 8

In the second binary tree, cost would be: 4*2 + 2*1 = 10

The minimum cost is 8; therefore, c[0,2] = 8

o When i=1 and j=3, then keys 20 and 30. There are two possible trees that can be made out from
these two keys shown below:

In the first binary tree, cost would be: 1*2 + 2*6 = 14

In the second binary tree, cost would be: 1*6 + 2*2 = 10

The minimum cost is 10; therefore, c[1,3] = 10

o When i=2 and j=4, we will consider the keys at 3 and 4, i.e., 30 and 40. There are two possible
trees that can be made out from these two keys shown as below:

In the first binary tree, cost would be: 1*6 + 2*3 = 12

In the second binary tree, cost would be: 1*3 + 2*6 = 15

The minimum cost is 12, therefore, c[2,4] = 12

Now we will calculate the values when j-i = 3

When j=3, i=0 then j-i = 3

When j=4, i=1 then j-i = 3

o When i=0, j=3 then we will consider three keys, i.e., 10, 20, and 30.

The following are the trees that can be made if 10 is considered as a root node.

In the above tree, 10 is the root node, 20 is the right child of node 10, and 30 is the right child of
node 20.
Cost would be: 1*4 + 2*2 + 3*6 = 26

In the above tree, 10 is the root node, 30 is the right child of node 10, and 20 is the left child of
node 20.

Cost would be: 1*4 + 2*6 + 3*2 = 22

The following tree can be created if 20 is considered as the root node.

In the above tree, 20 is the root node, 30 is the right child of node 20, and 10 is the left child of
node 20.

Cost would be: 1*2 + 4*2 + 6*2 = 22

The following are the trees that can be created if 30 is considered as the root node.
In the above tree, 30 is the root node, 20 is the left child of node 30, and 10 is the left child of
node 20.

Cost would be: 1*6 + 2*2 + 3*4 = 22

In the above tree, 30 is the root node, 10 is the left child of node 30 and 20 is the right child of
node 10.

Cost would be: 1*6 + 2*4 + 3*2 = 20

Therefore, the minimum cost is 20 which is the 3rd root. So, c[0,3] is equal to 20.

o When i=1 and j=4 then we will consider the keys 20, 30, 40
c[1,4] = min{ c[1,1] + c[2,4], c[1,2] + c[3,4], c[1,3] + c[4,4] } + 11

= min{0+12, 2+3, 10+0}+ 11

= min{12, 5, 10} + 11

The minimum value is 5; therefore, c[1,4] = 5+11 = 16

o Now we will calculate the values when j-i = 4

When j=4 and i=0 then j-i = 4

In this case, we will consider four keys, i.e., 10, 20, 30 and 40. The frequencies of 10, 20, 30 and
40 are 4, 2, 6 and 3 respectively.

w[0, 4] = 4 + 2 + 6 + 3 = 15

If we consider 10 as the root node then

C[0, 4] = min {c[0,0] + c[1,4]}+ w[0,4]

= min {0 + 16} + 15= 31

If we consider 20 as the root node then

C[0,4] = min{c[0,1] + c[2,4]} + w[0,4]

= min{4 + 12} + 15
= 16 + 15 = 31

If we consider 30 as the root node then,

C[0,4] = min{c[0,2] + c[3,4]} +w[0,4]

= min {8 + 3} + 15

= 26

If we consider 40 as the root node then,

C[0,4] = min{c[0,3] + c[4,4]} + w[0,4]

= min{20 + 0} + 15

= 35

In the above cases, we have observed that 26 is the minimum cost; therefore, c[0,4] is equal to
26.

The optimal binary tree can be created as:

General formula for calculating the minimum cost is:

C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j)

0/1 Knapsack problem

The 0/1 knapsack problem means that the items are either completely or no items are filled in a knapsack.
For example, we have two items having weights 2kg and 3kg, respectively. If we pick the 2kg item then
we cannot pick 1kg item from the 2kg item (item is not divisible); we have to pick the 2kg item
completely. This is a 0/1 knapsack problem in which either we pick the item completely or we will pick
that item. The 0/1 knapsack problem is solved by the dynamic programming.
 Example of 0/1 knapsack problem.

Consider the problem having weights and profits are:

Weights: {3, 4, 6, 5}

Profits: {2, 3, 1, 4}

The weight of the knapsack is 8 kg

The number of items is 4

The above problem can be solved by using the following method:

xi = {1, 0, 0, 1}

= {0, 0, 0, 1}

= {0, 1, 0, 1}

The above are the possible combinations. 1 denotes that the item is completely picked and 0
means that no item is picked. Since there are 4 items so possible combinations will be:

24 = 16; So. There are 16 possible combinations that can be made by using the above problem.
Once all the combinations are made, we have to select the combination that provides the
maximum profit.

Another approach to solve the problem is dynamic programming approach. In dynamic

programming approach, the complicated problem is divided into sub-problems, then we find
the solution of a sub-problem and the solution of the sub-problem will be used to find the
solution of a complex problem.
 How this problem can be solved by using the Dynamic programming
approach?

First,

we create a matrix shown as below:

0 1 2 3 4 5 6 7 8

In the above matrix, columns represent the weight, i.e., 8. The rows represent the profits and
weights of items. Here we have not taken the weight 8 directly, problem is divided into sub-
problems, i.e., 0, 1, 2, 3, 4, 5, 6, 7, 8. The solution of the sub-problems would be saved in the cells
and answer to the problem would be stored in the final cell. First, we write the weights in the
ascending order and profits according to their weights shown as below:

wi = {3, 4, 5, 6}

pi = {2, 3, 4, 1}

The first row and the first column would be 0 as there is no item for w=0

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0

2 0

3 0

4 0

When i=1, W=1

w1 = 3; Since we have only one item in the set having weight 3, but the capacity of the knapsack
is 1. We cannot fill the item of 3kg in the knapsack of capacity 1 kg so add 0 at M[1][1] shown as
below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0

2 0

3 0

4 0

When i = 1, W = 2

w1 = 3; Since we have only one item in the set having weight 3, but the capacity of the knapsack
is 2. We cannot fill the item of 3kg in the knapsack of capacity 2 kg so add 0 at M[1][2] shown as
below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0

2 0

3 0

4 0

When i=1, W=3

w1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is also 3; therefore, we can fill the knapsack with an item of weight equal to 3. We put
profit corresponding to the weight 3, i.e., 2 at M[1][3] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2

2 0

3 0

4 0

When i=1, W = 4

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack
is 4; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit
corresponding to the weight 3, i.e., 2 at M[1][4] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2

2 0

3 0

4 0

When i=1, W = 5

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack
is 5; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit
corresponding to the weight 3, i.e., 2 at M[1][5] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2

2 0

3 0

4 0

When i =1, W=6

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack
is 6; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit
corresponding to the weight 3, i.e., 2 at M[1][6] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2

2 0

3 0

4 0

When i=1, W = 7

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack
is 7; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit
corresponding to the weight 3, i.e., 2 at M[1][7] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2

2 0

3 0

4 0

When i =1, W =8

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack
is 8; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit
corresponding to the weight 3, i.e., 2 at M[1][8] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0

3 0

4 0

Now the value of 'i' gets incremented, and becomes 2.

When i =2, W = 1
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have only one item in the set having
weight equal to 4, and the weight of the knapsack is 1. We cannot put the item of weight 4 in a knapsack,
so we add 0 at M[2][1] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0

3 0

4 0
When i =2, W = 2
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have only one item in the set having
weight equal to 4, and the weight of the knapsack is 2. We cannot put the item of weight 4 in a knapsack,
so we add 0 at M[2][2] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0

3 0

4 0
When i =2, W = 3
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set having
weights 3 and 4, and the weight of the knapsack is 3. We can put the item of weight 3 in a knapsack, so
we add 2 at M[2][3] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2

3 0

4 0
When i =2, W = 4
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set having
weights 3 and 4, and the weight of the knapsack is 4. We can put item of weight 4 in a knapsack as the
profit corresponding to weight 4 is more than the item having weight 3, so we add 3 at M[2][4] shown as
below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3

3 0

4 0
When i = 2, W = 5
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set having
weights 3 and 4, and the weight of the knapsack is 5. We can put item of weight 4 in a knapsack and the
profit corresponding to weight is 3, so we add 3 at M[2][5] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3

3 0

4 0
When i = 2, W = 6
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set having
weights 3 and 4, and the weight of the knapsack is 6. We can put item of weight 4 in a knapsack and the
profit corresponding to weight is 3, so we add 3 at M[2][6] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3

3 0

4 0
When i = 2, W = 7
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set having
weights 3 and 4, and the weight of the knapsack is 7. We can put item of weight 4 and 3 in a knapsack
and the profits corresponding to weights are 2 and 3; therefore, the total profit is 5, so we add 5 at M[2][7]
shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 0 3 3 3 5

3 0

4 0
When i = 2, W = 8
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set having
weights 3 and 4, and the weight of the knapsack is 7. We can put item of weight 4 and 3 in a knapsack
and the profits corresponding to weights are 2 and 3; therefore, the total profit is 5, so we add 5 at M[2][7]
shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0

4 0
Now the value of 'i' gets incremented, and becomes 3.
When i = 3, W = 1
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set having
weights 3, 4, and 5, and the weight of the knapsack is 1. We cannot put neither of the items in a knapsack,
so we add 0 at M[3][1] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0

4 0
When i = 3, W = 2
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set having
weight 3, 4, and 5, and the weight of the knapsack is 1. We cannot put neither of the items in a knapsack,
so we add 0 at M[3][2] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0

4 0
When i = 3, W = 3
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of weight
3, 4, and 5 respectively and weight of the knapsack is 3. The item with a weight 3 can be put in the
knapsack and the profit corresponding to the item is 2, so we add 2 at M[3][3] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2

4 0
When i = 3, W = 4
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of weight
3, 4, and 5 respectively, and weight of the knapsack is 4. We can keep the item of either weight 3 or 4; the
profit (3) corresponding to the weight 4 is more than the profit corresponding to the weight 3 so we add 3
at M[3][4] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3

4 0
When i = 3, W = 5
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of weight
3, 4, and 5 respectively, and weight of the knapsack is 5. We can keep the item of either weight 3, 4 or 5;
the profit (3) corresponding to the weight 4 is more than the profits corresponding to the weight 3 and 5
so we add 3 at M[3][5] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3

4 0
When i =3, W = 6
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of weight
3, 4, and 5 respectively, and weight of the knapsack is 6. We can keep the item of either weight 3, 4 or 5;
the profit (3) corresponding to the weight 4 is more than the profits corresponding to the weight 3 and 5
so we add 3 at M[3][6] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3

4 0
When i =3, W = 7
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of weight
3, 4, and 5 respectively, and weight of the knapsack is 7. In this case, we can keep both the items of
weight 3 and 4, the sum of the profit would be equal to (2 + 3), i.e., 5, so we add 5 at M[3][7] shown as
below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5

4 0
When i = 3, W = 8
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of weight
3, 4, and 5 respectively, and the weight of the knapsack is 8. In this case, we can keep both the items of
weight 3 and 4, the sum of the profit would be equal to (2 + 3), i.e., 5, so we add 5 at M[3][8] shown as

below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0
Now the value of 'i' gets incremented and becomes 4.
When i = 4, W = 1
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of weights
3, 4, 5, and 6 respectively, and the weight of the knapsack is 1. The weight of all the items is more than
the weight of the knapsack, so we cannot add any item in the knapsack; Therefore, we add 0 at M[4][1]
shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0
When i = 4, W = 2
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of weights
3, 4, 5, and 6 respectively, and the weight of the knapsack is 2. The weight of all the items is more than
the weight of the knapsack, so we cannot add any item in the knapsack; Therefore, we add 0 at M[4][2]
shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0
When i = 4, W = 3
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of weights
3, 4, 5, and 6 respectively, and the weight of the knapsack is 3. The item with a weight 3 can be put in the
knapsack and the profit corresponding to the weight 4 is 2, so we will add 2 at M[4][3] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2
When i = 4, W = 4
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of weights
3, 4, 5, and 6 respectively, and the weight of the knapsack is 4. The item with a weight 4 can be put in the
knapsack and the profit corresponding to the weight 4 is 3, so we will add 3 at M[4][4] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3
When i = 4, W = 5
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of weights
3, 4, 5, and 6 respectively, and the weight of the knapsack is 5. The item with a weight 4 can be put in the
knapsack and the profit corresponding to the weight 4 is 3, so we will add 3 at M[4][5] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3 3
When i = 4, W = 6
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of weights
3, 4, 5, and 6 respectively, and the weight of the knapsack is 6. In this case, we can put the items in the
knapsack either of weight 3, 4, 5 or 6 but the profit, i.e., 4 corresponding to the weight 6 is highest among
all the items; therefore, we add 4 at M[4][6] shown as below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3 3 4
When i = 4, W = 7
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of weights
3, 4, 5, and 6 respectively, and the weight of the knapsack is 7. Here, if we add two items of weights 3
and 4 then it will produce the maximum profit, i.e., (2 + 3) equals to 5, so we add 5 at M[4][7] shown as
below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5
When i = 4, W = 8
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of weights
3, 4, 5, and 6 respectively, and the weight of the knapsack is 8. Here, if we add two items of weights 3
and 4 then it will produce the maximum profit, i.e., (2 + 3) equals to 5, so we add 5 at M[4][8] shown as
below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5
As we can observe in the above table that 5 is the maximum profit among all the entries. The pointer
points to the last row and the last column having 5 value. Now we will compare 5 value with the previous
row; if the previous row, i.e., i = 3 contains the same value 5 then the pointer will shift upwards. Since the
previous row contains the value 5 so the pointer will be shifted upwards as shown in the below table:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5
Again, we will compare the value 5 from the above row, i.e., i = 2. Since the above row contains the value
5 so the pointer will again be shifted upwards as shown in the below table:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5
Again, we will compare the value 5 from the above row, i.e., i = 1. Since the above row does not contain
the same value so we will consider the row i=1, and the weight corresponding to the row is 4. Therefore,
we have selected the weight 4 and we have rejected the weights 5 and 6 shown below:
x = { 1, 0, 0}
The profit corresponding to the weight is 3. Therefore, the remaining profit is (5 - 3) equals to 2. Now we
will compare this value 2 with the row i = 2. Since the row (i = 1) contains the value 2; therefore, the
pointer shifted upwards shown below:
0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5
Again we compare the value 2 with a above row, i.e., i = 1. Since the row i =0 does not contain the value
2, so row i = 1 will be selected and the weight corresponding to the i = 1 is 3 shown below:
X = {1, 1, 0, 0}
The profit corresponding to the weight is 2. Therefore, the remaining profit is 0. We compare 0 value with
the above row. Since the above row contains a 0 value but the profit corresponding to this row is 0. In this
problem, two weights are selected, i.e., 3 and 4 to maximize the profit.

All-Pairs Shortest Paths

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming algorithm used to discover the shortest
paths in a weighted graph, which includes negative weight cycles.

There are two important styles of dynamic programming:

1. Memoization
2. Tabulation
Memoization involves storing the outcomes of every subproblem in a cache, in order that they may be
reused later. Tabulation includes building a desk of answers to subproblems in a bottom-up manner,
beginning with the smallest subproblems and working as much as the larger ones. Dynamic programming
is utilized in an extensive range of packages, including optimization troubles, computational geometry,
gadget studying, and natural language processing.
Some well-known examples of problems that may be solved by the usage of dynamic programming
consist of the Fibonacci collection, the Knapsack trouble, and the shortest path problem.

Working of Floyd-Warshall Algorithm:

The set of rules works as follows:

1. Initialize a distance matrix D wherein D[i][j] represents the shortest distance between vertex i and
vertex j.
2. Set the diagonal entries of the matrix to 0, and all other entries to infinity.
 3. For every area (u,v) inside the graph, replace the gap matrix to mirror the weight of the brink:
D[u][v] = weight(u,v).
4. For every vertex okay in the graph, bear in mind all pairs of vertices (i,j) and check if the path
from i to j through k is shorter than the current best path. If it is, update the gap matrix: D[i][j] =
min(D[i][j], D[i][k] D[k][j]).
5. After all iterations, the matrix D will contain the shortest course distances between all pairs of
vertices.
Example:
Floyd-Warshall is an algorithm used to locate the shortest course between all pairs of vertices in
a weighted graph. It works by means of keeping a matrix of distances between each pair of vertices
and updating this matrix iteratively till the shortest paths are discovered.

Let's see at an example to illustrate how the Floyd-Warshall algorithm works:

Consider the following weighted graph:

Figure: A Weighted Graph

In this graph, the vertices are represented by letters (A, B, C, D), and the numbers on the edges
represent the weights of those edges.

To follow the Floyd-Warshall algorithm to this graph, we start by way of initializing a matrix of
distances among every pair of vertices. If two vertices are immediately related by using a side,
their distance is the load of that edge. If there may be no direct edge among vertices, their
distance is infinite.
In the first iteration of the set of rules, we keep in mind the possibility of the usage of vertex 1
(A) as an intermediate vertex in paths among all pairs of vertices. If the space from vertex 1 to
vertex 2 plus the space from vertex 2 to vertex three is much less than the present-day distance
from vertex 1 to vertex three, then we replace the matrix with this new distance. We try this for
each possible pair of vertices.

In the second iteration, we recollect the possibility to use of vertex 2 (B) as an intermediate vertex
in paths among all pairs of vertices. We replace the matrix in the same manner as earlier before.

In the third iteration, we consider the possibility of using vertex 3 (C) as an intermediate vertex
in paths between all pairs of vertices.
Finally, in the fourth and final iteration, we consider the possibility of using vertex 4 (D) as an
intermediate vertex in paths between all pairs of vertices.

After the fourth iteration, we have got the shortest path between every pair of vertices in the
graph. For example, the shortest path from vertex A to vertex D is 4, which is the value in the
matrix at row A and column D.

After the fourth iteration, we have got the shortest path between every pair of vertices in the
graph. For example, the shortest path from vertex A to vertex D is 4, which is the value in the
matrix at row A and column D.

Advantages of the Floyd-Warshall algorithm include:

1. It can discover the shortest direction between all pairs of vertices in a weighted graph, such as
graphs with negative edge weights.
2. It is an easy and smooth-to-put algorithm, making it accessible to developers of all skill ranges.
3. It is appropriate for both dense and sparse graphs.
4. It has a time complexity of O(N^3), that is relatively efficient for most real-international
applications.
5. It can be used to discover negative weight cycles in a graph.
Disadvantages of the Floyd-Warshall set of rules include:
1. It calls for a matrix of size N^2 to store the intermediate results, which may be prohibitively large
for extremely large graphs.
2. It is not the maximum green set of rules for fixing the all-pairs shortest path hassle in sure types of
graphs, inclusive of sparse graphs or graphs with non-bad part weights.
3. It won't be suitable for real-time packages or packages with strict reminiscence constraints, as it is
able to take a long term to compute the shortest paths in very huge graphs.
4. It can be less intuitive than different algorithms, which include Dijkstra's algorithm, or the
Bellman-Ford set of rules, making it more difficult to understand for some builders.
Applications of Floyd Warshall Algorithm:
The Floyd-Warshall algorithm is a dynamic programming algorithm used for finding the shortest course
among all pairs of vertices in a weighted graph. Here are some of the programs of the Floyd-Warshall
algorithm:
1. Routing Algorithms: The Floyd-Warshall algorithm is broadly utilized in routing algorithms,
along with within the OSPF (Open Shortest Path First) protocol utilized in Internet routing. It can
help decide the shortest route among two nodes in a network and is useful in locating the least
congested path.
2. Airline Networks: The Floyd-Warshall set of rules can also be utilized in airline networks to
locate the shortest path between two cities with the lowest cost. It can assist airways plan their
routes and limit fuel charges.
3. Traffic Networks: The algorithm is used to find the shortest path between points in a visitors'
network. It can help reduce congestion and improve the go with the flow of visitors in city areas.
4. Computer Networks: The Floyd-Warshall algorithm is likewise utilized in laptop networks to
decide the shortest course between hosts in a network. It can assist in minimizing community
latency and improve community overall performance.
5. Game Development: The set of rules may be used in game development to find the shortest
direction among two items in a sport world. It is beneficial in games in which the participant
desires to navigate through complex surroundings, together with a maze or a metropolis.
These are only some of the numerous applications of the Floyd-Warshall algorithm. It is a powerful
algorithm that can be applied in an extensive variety of fields to remedy a whole lot of troubles.

Travelling Salesman Problem

The traveling salesman problems abide by a salesman and a set of cities. The salesman has to visit every
one of the cities starting from a certain one (e.g., the hometown) and to return to the same city. The
challenge of the problem is that the traveling salesman needs to minimize the total length of the trip.
Suppose the cities are x1 x2 ........ xn where cost cij denotes the cost of travelling from city xi to xj. The
travelling salesperson problem is to find a route starting and ending at x 1 that will take in all cities with
the minimum cost.
Example: A newspaper agent daily drops the newspaper to the area assigned in such a manner that he has
to cover all the houses in the respective area with minimum travel cost. Compute the minimum travel
cost.
The area assigned to the agent where he has to drop the newspaper is shown in fig:
Solution: The cost- adjacency matrix of graph G is as follows:
costij =

The tour starts from area H1 and then select the minimum cost area reachable from H1.

Mark area H6 because it is the minimum cost area reachable from H1 and then select minimum cost area
reachable from H6.
Mark area H7 because it is the minimum cost area reachable from H6 and then select minimum cost area
reachable from H7.

Mark area H8 because it is the minimum cost area reachable from H8.

Mark area H5 because it is the minimum cost area reachable from H5.

Mark area H2 because it is the minimum cost area reachable from H2.
Mark area H3 because it is the minimum cost area reachable from H3 .

Mark area H 4 and then select the minimum cost area reachable from H 4 it is H1.So, using the greedy
strategy, we get the following.
4 3 2 4 3 2 1 6
H1 → H6 → H7 → H8 → H5 → H2 → H3 → H4 → H1.
Thus the minimum travel cost = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroids:
A matroid is an ordered pair M(S, I) satisfying the following conditions:
1. S is a finite set.
2. I is a nonempty family of subsets of S, called the independent subsets of S, such that if B ∈ I and
A ∈ I. We say that I is hereditary if it satisfies this property. Note that the empty set ∅ is
necessarily a member of I.
3. If A ∈ I, B ∈ I and |A| <|B|, then there is some element x ∈ B ? A such that A𝖴{x}∈I. We say that
M satisfies the exchange property.
We say that a matroid M (S, I) is weighted if there is an associated weight function w that assigns a
strictly positive weight w (x) to each element x ∈ S. The weight function w extends to a subset of S by
summation:
w (A) = ∑ x∈A w(x)
for any A ∈ S.
 Reliability design problem
In reliability design, the problem is to design a system that is composed of several
devices connected in series.

If we imagine that r1 is the reliability of the device.

Then the reliability of the function can be given by πr1.

If r1 = 0.99 and n = 10 that n devices are set in a series, 1 <= i <= 10, then reliability of
the whole system πri can be given as: Πri = 0.904

So, if we duplicate the devices at each stage then the reliability of the system can be
increased.

It can be said that multiple copies of the same device type are connected in parallel through the use of
switching circuits. Here, switching circuit determines which devices in any given group are functioning
properly. Then they make use of such devices at each stage, that result is increase in reliability at each
stage. If at each stage, there are mi similar types of devices Di, then the probability that all mi have a
malfunction is (1 - ri)^mi, which is very less.
And the reliability of the stage I becomes (1 – (1 - ri) ^mi). Thus, if ri = 0.99 and mi = 2, then the stage
reliability becomes 0.9999 which is almost equal to 1. Which is much better than that of the previous case
or we can say the reliability is little less than 1 - (1 - ri) ^mi because of less reliability of switching
circuits.

In reliability design, we try to use device duplication to maximize reliability. But this maximization
should be considered along with the cost.
Let c is the maximum allowable cost and ci be the cost of each unit of device i. Then the maximization
problem can be given as follows:
Maximize π Øi (mi) for 1 <= I <= n
Subject to:

mi>= 1 and integer 1 <= i <= n

Here, Øi (mi) denotes the reliability of the stage i.
The reliability of the system can be given as follows:
Π Øi (mi) for 1 <= i <= n
If we increase the number of devices at any stage beyond the certain limit, then also only the cost will
increase but the reliability could not increase.

************************************************