 ALL PAIR SHORTEST PATH (Floyd Warshall)

Algorithm
The Floyd-Warshall algorithm, named after its creators
Robert Floyd and Stephen Warshall, is a fundamental
algorithm in computer science and graph theory. It is used to
find the shortest paths between all pairs of nodes in a weighted
graph. This algorithm is highly efficient and can handle graphs
with both positive and negative edge weights, making it a
versatile tool for solving a wide range of network and
connectivity problems.

Floyd Warshall Algorithm:

The Floyd Warshall Algorithm is an all pair shortest path
algorithm unlike Dijkstra and Bellman Ford which are single
source shortest path algorithms. This algorithm works for both
the directed and undirected weighted graphs. But, it does not
work for the graphs with negative cycles (where the sum of the
edges in a cycle is negative). It follows Dynamic Programming
approach to check every possible path going via every possible
node in order to calculate shortest distance between every pair of
nodes.
Idea Behind Floyd Warshall Algorithm:
Suppose we have a graph G[][] with V vertices from 1 to N.
Now we have to evaluate a shortestPathMatrix[][] where
shortestPathMatrix[i][j] represents the shortest path between
vertices i and j.
Obviously the shortest path between i to j will have some k
number of intermediate nodes. The idea behind floyd warshall
algorithm is to treat each and every vertex from 1 to N as an
intermediate node one by one.
The following figure shows the above optimal substructure
property in floyd warshall algorithm:

Floyd Warshall Algorithm Algorithm:

 Initialize the solution matrix same as the input graph matrix

as a first step.

 Then update the solution matrix by considering all vertices

as an intermediate vertex.

 The idea is to pick all vertices one by one and updates all
shortest paths which include the picked vertex as an
intermediate vertex in the shortest path.

 When we pick vertex number k as an intermediate vertex,

we already have considered vertices {0, 1, 2, .. k-1} as
intermediate vertices.

 For every pair (i, j) of the source and destination vertices

respectively, there are two possible cases.
o k is not an intermediate vertex in shortest path from i
to j. We keep the value of dist[i][j] as it is.
 o k is an intermediate vertex in shortest path from i to j.
We update the value of dist[i][j] as dist[i][k] +
dist[k][j], if dist[i][j] > dist[i][k] + dist[k][j]
Pseudo-Code of Floyd Warshall Algorithm :
For k = 0 to n – 1
For i = 0 to n – 1
For j = 0 to n – 1
Distance[i, j] = min(Distance[i, j], Distance[i, k] + Distance[k,
j])
where i = source Node, j = Destination Node, k = Intermediate
Node
Illustration of Floyd Warshall Algorithm :
Suppose we have a graph as shown in the image:
Step 1: Initialize the Distance[][] matrix using the input graph
such that Distance[i][j]= weight of edge from i to j, also
Distance[i][j] = Infinity if there is no edge from i to j.

Step 2: Treat node A as an intermediate node and calculate the

Distance[][] for every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to
A) + (Distance from A to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][A] +
Distance[A][j])
Step 3: Treat node B as an intermediate node and calculate the
Distance[][] for every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to
B) + (Distance from B to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][B] +
Distance[B][j])
Step 4: Treat node C as an intermediate node and calculate the
Distance[][] for every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to
C) + (Distance from C to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][C] +
Distance[C][j])
Step 5: Treat node D as an intermediate node and calculate the
Distance[][] for every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to
D) + (Distance from D to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][D] +
Distance[D][j])

Step 6: Treat node E as an intermediate node and calculate the

Distance[][] for every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to
E) + (Distance from E to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][E] +
Distance[E][j])

Step 7: Since all the nodes have been treated as an intermediate

node, we can now return the updated Distance[][] matrix as our
answer matrix.
Below is the implementation of the above approach:
// C++ Program for Floyd Warshall Algorithm
#include <bits/stdc++.h>
using namespace std;

// Number of vertices in the graph

#define V 4

/* Define Infinite as a large enough

value.This value will be used for
vertices not connected to each other */
#define INF 99999

// A function to print the solution matrix

void printSolution(int dist[][V]);
// Solves the all-pairs shortest path
// problem using Floyd Warshall algorithm
void floydWarshall(int dist[][V])
{

int i, j, k;

/* Add all vertices one by one to

the set of intermediate vertices.
---> Before start of an iteration,
we have shortest distances between all
pairs of vertices such that the
shortest distances consider only the
vertices in set {0, 1, 2, .. k-1} as
intermediate vertices.
----> After the end of an iteration,
vertex no. k is added to the set of
intermediate vertices and the set becomes {0, 1, 2, ..
k} */
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++) {
// If vertex k is on the shortest path from
// i to j, then update the value of
// dist[i][j]
if (dist[i][j] > (dist[i][k] + dist[k][j])
&& (dist[k][j] != INF
&& dist[i][k] != INF))
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

// Print the shortest distance matrix

printSolution(dist);
}

/* A utility function to print solution */

void printSolution(int dist[][V])
{
cout << "The following matrix shows the shortest "
"distances"
" between every pair of vertices \n";
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
cout << "INF"
<< " ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}

// Driver's code
int main()
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5| |
| |1
\|/ |
(1)------->(2)
3 */
int graph[V][V] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };

// Function call
floydWarshall(graph);
return 0;
}

// This code is contributed by Mythri J L

Output
The following matrix shows the shortest distances between
every pair of vertices
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
Complexity Analysis of Floyd Warshall Algorithm:
  Time Complexity: O(V3), where V is the number of
vertices in the graph and we run three nested loops each of
size V

 Auxiliary Space: O(V2), to create a 2-D matrix in order to

store the shortest distance for each pair of nodes.

 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.

 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

 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

 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

 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.

 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
  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)
  Travelling Salesperson Algorithm
The travelling salesman problem is a graph computational
problem where the salesman needs to visit all cities (represented
using nodes in a graph) in a list just once and the distances
(represented using edges in the graph) between all these cities
are known. The solution that is needed to be found for this
problem is the shortest possible route in which the salesman
visits all the cities and returns to the origin city.
If you look at the graph below, considering that the salesman
starts from the vertex ‘a’, they need to travel through all the
remaining vertices b, c, d, e, f and get back to ‘a’ while making
sure that the cost taken is minimum.

There are various approaches to find the solution to the

travelling salesman problem: naive approach, greedy approach,
dynamic programming approach, etc. In this tutorial we will be
learning about solving travelling salesman problem using greedy
approach.
Travelling Salesperson Algorithm
As the definition for greedy approach states, we need to find the
best optimal solution locally to figure out the global optimal
solution. The inputs taken by the algorithm are the graph G {V,
E}, where V is the set of vertices and E is the set of edges. The
shortest path of graph G starting from one vertex returning to the
same vertex is obtained as the output.
Algorithm

 Travelling salesman problem takes a graph G {V, E} as an

input and declare another graph as the output (say G’)
which will record the path the salesman is going to take
from one node to another.
 The algorithm begins by sorting all the edges in the input
graph G from the least distance to the largest distance.
 The first edge selected is the edge with least distance, and
one of the two vertices (say A and B) being the origin node
(say A).
 Then among the adjacent edges of the node other than the
origin node (B), find the least cost edge and add it onto the
output graph.
 Continue the process with further nodes making sure there
are no cycles in the output graph and the path reaches back
to the origin node A.
 However, if the origin is mentioned in the given problem,
then the solution must always start from that node only. Let
us look at some example problems to understand this better.
Examples

Consider the following graph with six cities and the distances
between them −

From the given graph, since the origin is already mentioned, the
solution must always start from that node. Among the edges
leading from A, A → B has the shortest distance.

Then, B → C has the shortest and only edge between, therefore

it is included in the output graph.
There’s only one edge between C → D, therefore it is added to
the output graph.

There’s two outward edges from D. Even though, D → B has

lower distance than D → E, B is already visited once and it
would form a cycle if added to the output graph. Therefore, D →
E is added into the output graph.
There’s only one edge from e, that is E → F. Therefore, it is
added into the output graph.
Again, even though F → C has lower distance than F → A, F →
A is added into the output graph in order to avoid the cycle that
would form and C is already visited once.

The shortest path that originates and ends at A is A → B → C

→D→E→F→A
The cost of the path is: 16 + 21 + 12 + 15 + 16 + 34 = 114.
Even though, the cost of path could be decreased if it originates
from other nodes but the question is not raised with respect to
that.

Example
The complete implementation of Travelling Salesman Problem
using Greedy Approach is given below −
Open Compiler
#include <stdio.h>
int tsp_g[10][10] = {
{12, 30, 33, 10, 45},
{56, 22, 9, 15, 18},
{29, 13, 8, 5, 12},
{33, 28, 16, 10, 3},
{1, 4, 30, 24, 20}
};
int visited[10], n, cost = 0;

/* creating a function to generate the shortest path */

void travellingsalesman(int c){
int k, adj_vertex = 999;
int min = 999;

/* marking the vertices visited in an assigned array */

visited[c] = 1;

/* displaying the shortest path */

printf("%d ", c + 1);

/* checking the minimum cost edge in the graph */

for(k = 0; k < n; k++) {
if((tsp_g[c][k] != 0) && (visited[k] == 0)) {
if(tsp_g[c][k] < min) {
min = tsp_g[c][k];
adj_vertex = k;
}
}
}
if(min != 999) {
cost = cost + min;
}
if(adj_vertex == 999) {
adj_vertex = 0;
printf("%d", adj_vertex + 1);
cost = cost + tsp_g[c][adj_vertex];
return;
}
travellingsalesman(adj_vertex);
}

/* main function */
int main(){
int i, j;
n = 5;
for(i = 0; i < n; i++) {
visited[i] = 0;
}
printf("Shortest Path: ");
travellingsalesman(0);
printf("\nMinimum Cost: ");
printf("%d\n", cost);
return 0;
}
Output
Shortest Path: 1 4 5 2 3 1
Minimum Cost: 55
  Knapsack Problem

the fractional knapsack problem using the greedy approach,

earlier in this tutorial. It is shown that Greedy approach gives an
optimal solution for Fractional Knapsack. However, this chapter
will cover 0-1 Knapsack problem using dynamic programming
approach and its analysis.
Unlike in fractional knapsack, the items are always stored fully
without using the fractional part of them. Its either the item is
added to the knapsack or not. That is why, this method is known
as the 0-1 Knapsack problem.
Hence, in case of 0-1 Knapsack, the value of xi can be either 0 or
1, where other constraints remain the same.
0-1 Knapsack cannot be solved by Greedy approach. Greedy
approach does not ensure an optimal solution in this method. In
many instances, Greedy approach may give an optimal solution.
0-1 Knapsack Algorithm
Problem Statement − A thief is robbing a store and can carry a
maximal weight of W into his knapsack. There are n items and
weight of ith item is wi and the profit of selecting this item is pi.
What items should the thief take?
Let i be the highest-numbered item in an optimal solution S for
W dollars. Then S’ = S − {i} is an optimal solution for W – wi
dollars and the value to the solution S is Vi plus the value of the
sub-problem.
We can express this fact in the following formula: define c[i, w]
to be the solution for items 1,2, … , i and the maximum weight
w.
The algorithm takes the following inputs

 The maximum weight W

 The number of items n
 The two sequences v = <v1, v2, …, vn> and w = <w1, w2,
…, wn>
The set of items to take can be deduced from the table, starting
at c[n, w] and tracing backwards where the optimal values came
from.
If c[i, w] = c[i-1, w], then item i is not part of the solution, and
we continue tracing with c[i-1, w]. Otherwise, item i is part of
the solution, and we continue tracing with c [i-1, w-W].
Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
c[0, w] = 0
for i = 1 to n do
c[i, 0] = 0
for w = 1 to W do
if wi ≤ w then
if vi + c[i-1, w-wi] then
c[i, w] = vi + c[i-1, w-wi]
else c[i, w] = c[i-1, w]
else
c[i, w] = c[i-1, w]
The following examples will establish our statement.
Example

Let us consider that the capacity of the knapsack is W = 8 and

the items are as shown in the following table.

Item ABCD

Profit 2 4 7 10

Weight 1 3 5 7

Solution

Using the greedy approach of 0-1 knapsack, the weight that’s

stored in the knapsack would be A+B = 4 with the maximum
profit 2 + 4 = 6. But, that solution would not be the optimal
solution.
Therefore, dynamic programming must be adopted to solve 0-1
knapsack problems.
Step 1
Construct an adjacency table with maximum weight of knapsack
as rows and items with respective weights and profits as
columns.
Values to be stored in the table are cumulative profits of the
items whose weights do not exceed the maximum weight of the
knapsack (designated values of each row)
So we add zeroes to the 0th row and 0th column because if the
weight of item is 0, then it weighs nothing; if the maximum
weight of knapsack is 0, then no item can be added into the
knapsack.

The remaining values are filled with the maximum profit

achievable with respect to the items and weight per column that
can be stored in the knapsack.
The formula to store the profit values is −
c[i,w]=max{c[i−1,w−w[i]]+P[i]}

By computing all the values using the formula, the table

obtained would be −
To find the items to be added in the knapsack, recognize the
maximum profit from the table and identify the items that make
up the profit, in this example, its {1, 7}.
The optimal solution is {1, 7} with the maximum profit is 12.
Analysis
This algorithm takes Ɵ(n.w) times as table c has (n+1).(w+1)
entries, where each entry requires Ɵ(1) time to compute.

Implementation
Following is the final implementation of 0-1 Knapsack
Algorithm using Dynamic Programming Approach.

Open Compiler
#include <stdio.h>
#include <string.h>
int findMax(int n1, int n2){
if(n1>n2) {
return n1;
} else {
return n2;
}
}
int knapsack(int W, int wt[], int val[], int n){
int K[n+1][W+1];
for(int i = 0; i<=n; i++) {
for(int w = 0; w<=W; w++) {
if(i == 0 || w == 0) {
K[i][w] = 0;
} else if(wt[i-1] <= w) {
K[i][w] = findMax(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
} else {
K[i][w] = K[i-1][w];
}
}
}
return K[n][W];
}
int main(){
int val[5] = {70, 20, 50};
int wt[5] = {11, 12, 13};
int W = 30;
int len = sizeof val / sizeof val[0];
printf("Maximum Profit achieved with this knapsack: %d",
knapsack(W, wt, val, len));
}
Output
Maximum Profit achieved with this knapsack: 120

 Matrix Chain Multiplication Algorithm

Matrix Chain Multiplication is an algorithm that is applied to

determine the lowest cost way for multiplying matrices. The
actual multiplication is done using the standard way of
multiplying the matrices, i.e., it follows the basic rule that the
number of rows in one matrix must be equal to the number of
columns in another matrix. Hence, multiple scalar
multiplications must be done to achieve the product.
To brief it further, consider matrices A, B, C, and D, to be
multiplied; hence, the multiplication is done using the standard
matrix multiplication. There are multiple combinations of the
matrices found while using the standard approach since matrix
multiplication is associative. For instance, there are five ways to
multiply the four matrices given above −

 (A(B(CD)))
 (A((BC)D))
 ((AB)(CD))
 ((A(BC))D)
  (((AB)C)D)
Now, if the size of matrices A, B, C, and D are l × m, m × n, n
× p, p × q respectively, then the number of scalar
multiplications performed will be lmnpq. But the cost of the
matrices change based on the rows and columns present in it.
Suppose, the values of l, m, n, p, q are 5, 10, 15, 20, 25
respectively, the cost of (A(B(CD))) is 5 × 100 × 25 = 12,500;
however, the cost of (A((BC)D)) is 10 × 25 × 37 = 9,250.
So, dynamic programming approach of the matrix chain
multiplication is adopted in order to find the combination with
the lowest cost.
Matrix Chain Multiplication Algorithm
Matrix chain multiplication algorithm is only applied to find the
minimum cost way to multiply a sequence of matrices.
Therefore, the input taken by the algorithm is the sequence of
matrices while the output achieved is the lowest cost
parenthesization.
Algorithm

 Count the number of parenthesizations. Find the number of

ways in which the input matrices can be multiplied using
the formulae −
P(n)={1∑n−1k=1P(k)P(n−k)ifn=1ifn≥2

(or)
P(n)={2(n−1)Cn−1n1ifn≥2ifn=1
  Once the parenthesization is done, the optimal substructure
must be devised as the first step of dynamic programming
approach so the final product achieved is optimal. In matrix
chain multiplication, the optimal substructure is found by
dividing the sequence of matrices A[i….j] into two parts
A[i,k] and A[k+1,j]. It must be ensured that the parts are
divided in such a way that optimal solution is achieved.
 Using the formula,
C[i,j]={0mini≤k<j{C[i,k]+C[k+1,j]+di−1dkdjifi=jifi<j

 find the lowest cost parenthesization of the sequence of

matrices by constructing cost tables and corresponding k
values table.
 Once the lowest cost is found, print the corresponding
parenthesization as the output.
Pseudocode

Pseudocode to find the lowest cost of all the possible

parenthesizations −
MATRIX-CHAIN-MULTIPLICATION(p)
n = p.length ─ 1
let m[1…n, 1…n] and s[1…n ─ 1, 2…n] be new matrices
for i = 1 to n
m[i, i] = 0
for l = 2 to n // l is the chain length
for i = 1 to n - l + 1
j=i+l-1
m[i, j] = ∞
for k = i to j - 1
q = m[i, k] + m[k + 1, j] + pi-1pkpj
if q < m[i, j]
m[i, j] = q
s[i, j] = k
return m and s
Pseudocode to print the optimal output parenthesization −
PRINT-OPTIMAL-OUTPUT(s, i, j )
if i == j
print “A”i
else print “(”
PRINT-OPTIMAL-OUTPUT(s, i, s[i, j])
PRINT-OPTIMAL-OUTPUT(s, s[i, j] + 1, j)
print “)”
Example

The application of dynamic programming formula is slightly

different from the theory; to understand it better let us look at
few examples below.
A sequence of matrices A, B, C, D with dimensions 5 × 10, 10 ×
15, 15 × 20, 20 × 25 are set to be multiplied. Find the lowest
cost parenthesization to multiply the given matrices using matrix
chain multiplication.
Solution

Given matrices and their corresponding dimensions are −

A5×10×B10×15×C15×20×D20×25
Find the count of parenthesization of the 4 matrices, i.e. n = 4.
Using the formula, P(n)={1∑n−1k=1P(k)P(n−k)ifn=1ifn≥2
Since n = 4 ≥ 2, apply the second case of the formula −
P(n)=∑k=1n−1P(k)P(n−k)
P(4)=∑k=13P(k)P(4−k)
P(4)=P(1)P(3)+P(2)P(2)+P(3)P(1)

If P(1) = 1 and P(2) is also equal to 1, P(4) will be calculated

based on the P(3) value. Therefore, P(3) needs to determined
first.
P(3)=P(1)P(2)+P(2)P(1)
=1+1=2

Therefore,
P(4)=P(1)P(3)+P(2)P(2)+P(3)P(1)
=2+1+2=5

Among these 5 combinations of parenthesis, the matrix chain

multiplicatiion algorithm must find the lowest cost parenthesis.
Step 1
The table above is known as a cost table, where all the cost
values calculated from the different combinations of parenthesis
are stored.
Another table is also created to store the k values obtained at the
minimum cost of each combination.
Step 2
Applying the dynamic programming approach formula find the
costs of various parenthesizations,
C[i,j]={0mini≤k<j{C[i,k]+C[k+1,j]+di−1dkdjifi=jifi<j

C[1,1]=0
C[2,2]=0
C[3,3]=0
C[4,4]=0

Step 3
Applying the dynamic approach formula only in the upper
triangular values of the cost table, since i < j always.
C[1,2]=min1≤k<2{C[1,1]+C[2,2]+d0d1d2}

 C[1,2]=0+0+(5×10×15)
C[1,2]=750


C[2,3]=min2≤k<3{C[2,2]+C[3,3]+d1d2d3}

 C[2,3]=0+0+(10×15×20)
C[2,3]=3000


C[3,4]=min3≤k<4{C[3,3]+C[4,4]+d2d3d4}

 C[3,4]=0+0+(15×20×25)
C[3,4]=7500

Step 4
Find the values of [1, 3] and [2, 4] in this step. The cost table is
always filled diagonally step-wise.
C[2,4]=min2≤k<4{C[2,2]+C[3,4]+d1d2d4,C[2,3]+C[4,4]+d1d3
d4}

 C[2,4]=min{(0+7500+(10×15×20)),(3000+5000)}
C[2,4]=8000


C[1,3]=min1≤k<3{C[1,1]+C[2,3]+d0d1d3,C[1,2]+C[3,3]+d0d2
d3}

 C[1,3]=min{(0+3000+1000),(1500+0+750)}
C[1,3]=2250
 

Step 5
Now compute the final element of the cost table to compare the
lowest cost parenthesization.
C[1,4]=min1≤k<4{C[1,1]+C[2,4]+d0d1d4,C[1,2]+C[3,4]+d1d2
d4,C[1,3]+C[4,4]+d1d3d4}

 C[1,4]=min{0+8000+1250,750+7500+1875,2200+0+2500}
C[1,4]=4700

Now that all the values in cost table are computed, the final step
is to parethesize the sequence of matrices. For that, k table needs
to be constructed with the minimum value of ‘k’ corresponding
to every parenthesis.
Parenthesization

Based on the lowest cost values from the cost table and their
corresponding k values, let us add parenthesis on the sequence
of matrices.
The lowest cost value at [1, 4] is achieved when k = 3, therefore,
the first parenthesization must be done at 3.
(ABC)(D)
The lowest cost value at [1, 3] is achieved when k = 2, therefore
the next parenthesization is done at 2.
((AB)C)(D)
The lowest cost value at [1, 2] is achieved when k = 1, therefore
the next parenthesization is done at 1. But the parenthesization
needs at least two matrices to be multiplied so we do not divide
further.
((AB)(C))(D)
Since, the sequence cannot be parenthesized further, the final
solution of matrix chain multiplication is ((AB)C)(D).

Implementation
Following is the final implementation of Matrix Chain
Multiplication Algorithm to calculate the minimum number of
ways several matrices can be multiplied using dynamic
programming −
C C++ Java Python
Open Compiler
#include <stdio.h>
#include <string.h>
#define INT_MAX 999999
int mc[50][50];
int min(int a, int b){
if(a < b)
return a;
else
return b;
}
int DynamicProgramming(int c[], int i, int j){
if (i == j) {
return 0;
}
if (mc[i][j] != -1) {
return
mc[i][j];
}
mc[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
mc[i][j] = min(mc[i][j], DynamicProgramming(c, i, k) +
DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]);
}
return mc[i][j];
}
int Matrix(int c[], int n){
int i = 1, j = n - 1;
return DynamicProgramming(c, i, j);
}
int main(){
int arr[] = { 23, 26, 27, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
memset(mc, -1, sizeof mc);
printf("Minimum number of multiplications is: %d", Matrix(arr,
n));
}
Output
Minimum number of multiplications is: 26000