Optimal Binary Search Trees (OBST)

• Suppose we are searching a word from a dictionary.

• For every required word we are looking up in the dictionary then it
becomes time consuming process.
• To perform this look up more efficiently we can build the binary
search tree of common words as key element.
• We can make this binary search tree efficient by arranging frequently
used words nearer to the root and less frequently words away from the
root.
• Such a binary search tree makes our task more simplified as well as
efficient.
• This type of binary search tree is also called optimal binary search tree
(OBST).
Optimal Binary Search Trees (OBST)
• Let {a1, a2, a3, ……, an} be a set of keys such that a1 < a2 < a3.
• Let p(i) be the probability of successful search and q(i) be the
probability of unsuccessful search for an key element i.
 Optimal Binary Search Trees (OBST)
• Let us consider the three key elements 10, 20 and 30.
• The binary search trees for the above keys have been shown below.

10 1 1 10 1 20 30 1 1 30

20 2 2 30 10 30 10 2 20 2
2 2
Average No. of
30 3 20 3 3 20 10 3
Comparisons =
(1+2+2)/3 = 5/3 =
1.6
Average No. of Average No. of Average No. of Average No. of
Comparisons = Comparisons = Comparisons = Comparisons =
(1+2+3)/3 = 6/3 = 2 (1+2+3)/3 = 6/3 = 2 (1+2+3)/3 = 6/3 = 2 (1+2+3)/3 = 6/3 = 2
 Optimal Binary Search Trees (OBST)
• Let us consider the three key elements 10, 20 and 30.
• Let the frequencies associated with the key elements are 3, 2 and 5 respectively.
• The binary search trees for the above keys have been shown below.

10 1*3 1*3 10 1 20 30 1 1 30

20 2*2 2*5 30 10 30 10 2 20 2
2 2

30 3*5 20 3*2 3 20 10 3
BST3

BST1 BST2 BST4 BST5

 Optimal Binary Search Trees (OBST)
• By considering the frequency the cost of the Binary search trees
have been calculated as below.
• Cost of Binary Search Tree 1 = 3 x 1 + 2 x 2 + 5 x 3 = 22
• Cost of Binary Search Tree 2 = 3 x 1 + 5 x 2 + 2 x 3 = 19 30 1
• Cost of Binary Search Tree 3 = 2 x 1 + 3 x 2 + 5 x 2 = 18
• Cost of Binary Search Tree 4 = 5 x 1 + 3 x 2 + 2 x 3 = 17
10 2
• Cost of Binary Search Tree 5 = 5 x 1 + 2 x 2 + 3 x 3 = 18
• The Binary Search Tree 4 is having minimum cost.
3 20
• Therefore Binary Search Tree 4 has been considered as OBST.
Optimal Binary Search Trees (OBST)
• Example
• Construct the optimal binary search tree for the following data: n = 4,
(a1, a2, a3, a4) = (do, if, int, while), p(1:4) = (3, 3, 1, 1) and q(0:4) =
2, 3, 1, 1, 1)
• Solution
• Computation of W, C and r has been carried out using the following
formulae.
• wi, i = qi
• ri. i = 0
• ci, i = 0
Optimal Binary Search Trees (OBST)
• wi, i+1 = qi + qi+1 + pi+1
• ri. i+1 = i+1
• ci, i+1 = qi + qi+1 + pi+1 W Table
• wi, j = wi, j-1 + pj + qj i→
0 1 2 3 4
• ri. j = k
l=j-i 0
• ↓ 1
• Construction of the W Table 2
3
• The rows of the W table
4
represents the length l of the tree.
• The length l will be given by
• l=j–i
 Optimal Binary Search Trees (OBST)
W Table
• For length of the tree 0 i→
•l=j–i=0 0 1 2 3 4

• For i = 0, j = 0, w0,0 = q0 = 2 l=j-i

0 w0,0 = w1,1 = w2,2 = w3,3 = w4,4 =
2 3 1 1 1
• For i = 1, j = 1, w1,1 = q1 = 3 ↓
1
• For i = 2, j = 2, w2,2 = q2 = 1 2

• For i = 3, j = 3, w3,3 = q3 = 1 3
4
• For i = 4, j = 4, w4,4 = q4 = 1
wi, i = qi
wi, i+1 = qi + qi+1 + pi+1
wi, j = wi, j-1 + pj + qj
 Optimal Binary Search Trees (OBST)
W Table
• For length of the tree 1 i→
•l=j–i=1 0 1 2 3 4

• For i = 0, j = 1, w0,1 = q0 + q1 + p1 0 w0,0 = w1,1 = w2,2 = w3,3 = w4,4 =

l=j-i 2 3 1 1 1
=8 ↓ 1 w0,1 = w1,2 = w2,3 = w3,4 =
• For i = 1, j = 2, w1,2 = q1 + q2 + p2 = 8 7 3 3
7 2

• For i = 2, j = 3, w2,3 = q2 + q3 + p3 = 3

3 4

• For i = 3, j = 4, w3,4 = q3 + q4 + p4 = wi, i = qi

3 wi, i+1 = qi + qi+1 + pi+1
wi, j = wi, j-1 + pj + qj
 Optimal Binary Search Trees (OBST)
W Table
• For length of the tree 2
i→
• l=j–i=2
0 1 2 3 4
• For i = 0, j=2, w0,2 = w0,1 + p2 + q2 = 0 w0,0 = w1,1 = w2,2 = w3,3 = w4,4 =
12 2 3 1 1 1
• For i = 1, j=3, w1,3 = w1,2 + p3 + q3 = 9 l=j-i 1 w0,1 = w1,2 = w2,3 = w3,4 =
↓ 8 7 3 3
• For i = 2, j=4, w2,4 = w2,3 + p4 + q4 = 5
2 w0,2 = w1,3 = w2,4 =
• For length of the tree 3 12 9 5
• l=j–i=3 3 w0,3 = w1,4 =
14 11
• For i = 0, j=3, w0,3 = w0,2 + p3 + q3 =
4
14
• For i = 1, j=4, w1,4 = w1,3 + p4 + q4 =
11 wi, j = wi, j-1 + pj + qj
 Optimal Binary Search Trees (OBST)
W Table
• For length of the tree 4 i→
•l=j–i=4 0 1 2 3 4

• For i = 0, j=4, w0,4 = w0,3 + p4 + q4 = 0 w0,0 = w1,1 = w2,2 = w3,3 = w4,4 =

2 3 1 1 1
16
l=j-i 1 w0,1 = w1,2 = w2,3 = w3,4 =
• Computation of C and r Table ↓ 8 7 3 3
2 w0,2 = w1,3 = w2,4 =
12 9 5
3 W0,3 = w1,4 =
14 11
4 w0,4 =
16

wi, j = wi, j-1 + pj + qj

 Optimal Binary Search Trees (OBST)
C and r Table
• Computation of C and r Table i→
• For length of the tree 0 0 1 2 3 4

•l=j–i=0 l=j-i
0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0
r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
• For i = 0, j=0, c0,0 = 0, r0,0 = 0 ↓
1
• For i = 1, j=1, c1,1 = 0, r1,1 = 0 2

• For i = 2, j=2, c2,2 = 0, r2,2 = 0 3

4
• For i = 3, j=3, c3,3 = 0, r3,3 = 0
• For i = 4, j=4, c4,4 = 0, r4,4 = 0

ri. i = 0
ci, i = 0
 Optimal Binary Search Trees (OBST)
C and r Table
• For length of the tree 1 i→
•l=j–i=1 0 1 2 3 4

• For i = 0, j=1, c0,1 = q0 + q1 +p1 l=j-i

0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0
r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
=8 ↓
1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
• For i = 1, j=2, c1,2 = q1 + q2 +p2 2
=7 3
• For i = 2, j=3, c2,3 = q2 + q3 +p3 4
=3
• For i = 3, j=4, c3,4 = q3 + q4 +p4
=3 ri. i+1 = i+1
ci, i+1 = qi + qi+1 + pi+1
 Optimal Binary Search Trees (OBST)
C and r Table
• For length of the tree 1 i→
•l=j–i=1 0 1 2 3 4

• For i = 0, j=1, r0,1 = 0 + 1 =1 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0

l=j-i r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
• For i = 1, j=2, r1,2 = 1 + 1 = 2 ↓ 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
• For i = 2, j=3, r2,3 = 2 + 1 = 3 r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2
• For i = 3, j=4, r3,4 = 3 + 1 = 4 3
4

ri. i+1 = i+1

ci, i+1 = qi + qi+1 + pi+1
 Optimal Binary Search Trees (OBST)
C and r Table
• For length of the tree 2 i→
•l=j–i=2 0 1 2 3 4

• For i = 0, j=2 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0

r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
• l=j-i
↓ 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19
• r0,2= 1
3
4
• c0,2 = 12 + 7 = 19
• r0,2 = k = 1

ri. j = k
 Optimal Binary Search Trees (OBST)
C and r Table
• For length of the tree 2 i→
•l=j–i=2 0 1 2 3 4

• For i = 1, j=3 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0

r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
• l=j-i
↓ 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12
• r0,2= 1 r1,3 = 2
3
4
• c1,3 = 9 + 3 = 12
• r1,3 = k = 2
 Optimal Binary Search Trees (OBST)
C and r Table
• For length of the tree 2 i→
•l=j–i=2 0 1 2 3 4

• For i = 2, j=4 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0

r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
• l=j-i
↓ 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
• r0,2= 1 r1,3 = 2 r2,4 = 3
3
4
• c2,4 = 5 + 3 = 8
• r2,4 = k = 3
 Optimal Binary Search Trees (OBST)
C and r Table
• For length of the tree 3 i→
•l=j–i=3 0 1 2 3 4

• For i = 0, j=3 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0

r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
l=j-i 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
↓ r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
• r0,2= 1 r1,3 = 2 r2,4 = 3
3 c0,3 = 25
r0,3= 2
• c0,3 = 14 + 11 = 25 4

• r0,3 = k = 2
 Optimal Binary Search Trees (OBST)
C and r Table
• For length of the tree 3 i→
•l=j–i=3 0 1 2 3 4

• For i = 1, j=4 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0

r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
l=j-i 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
↓ r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
• r0,2= 1 r1,3 = 2 r2,4 = 3
3 c0,3 = 25 c1,4 = 19
r0,3= 2 r1,4 = 2
• c1,4 = 11 + 8 = 19 4

• r1,4 = k = 2
 Optimal Binary Search Trees (OBST)
C and r Table
• For length of the tree 4 i→
•l=j–i=4 0 1 2 3 4

• For i = 0, j=4 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0

r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
l=j-i 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
↓ r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
r0,2= 1 r1,3 = 2 r2,4 = 3
3 c0,3 = 25 C1,4 = 19
r0,3= 2 r1,4 = 2
4 c0,4 = 32
r0,4= 2
• c0,4 = 16 + 16 = 32
• r0,4 = k = 2
 Optimal Binary Search Trees (OBST)
C and r Table
• The root of the Binary Search
i→
Tree will be given by r0,n.
0 1 2 3 4
• From the C and r table r0,4 = 2.
0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0
• Therefore a2 becomes the root r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
of the BST. l=j-i 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
↓
• ri, k-1 becomes the left child. r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
• rk,j becomes the right child. r0,2= 1 r1,3 = 2 r2,4 = 3
3 c0,3 = 25 C1,4 = 19
r0,3= 2 r1,4 = 2
• The binary search tree can be 4 c0,4 = 32
constructed using the above r0,4= 2
formulation has been shown
below.
 Optimal Binary Search Trees (OBST)
C and r Table
i→
0 1 2 3 4
r0,4 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0
r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
r0,1 r2,4 l=j-i 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
↓ r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
r0,0 r1,1 r2,2 r0,2= 1 r1,3 = 2 r2,4 = 3
r3,4
3 c0,3 = 25 C1,4 = 19
r0,3= 2 r1,4 = 2
r3,3 4 c0,4 = 32
r4,4
r0,4= 2
 Optimal Binary Search Trees (OBST)
C and r Table
i→
0 1 2 3 4
r0,4 0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0
r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
r0,1 r2,4 l=j-i 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
↓ r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
r0,0 r1,1 r2,2 r0,2= 1 r1,3 = 2 r2,4 = 3
r3,4
3 c0,3 = 25 C1,4 = 19
r0,3= 2 r1,4 = 2
r3,3 4 c0,4 = 32
r4,4
r0,4= 2
 Optimal Binary Search Trees (OBST)
C and r Table
Substituting the root table element values we obtain the
i→
following Binary search Tree.
0 1 2 3 4
0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0
r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
2 l=j-i 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
↓ r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
1 3 r0,2= 1 r1,3 = 2 r2,4 = 3
3 c0,3 = 25 C1,4 = 19
0 r0,3= 2 r1,4 = 2
0 0 4
4 c0,4 = 32
r0,4= 2

0 0
 Optimal Binary Search Trees (OBST)
C and r Table
Substituting the corresponding the key elements we
i→
obtain the following Optimal Binary search Tree.
0 1 2 3 4
0 c0,0 = 0 c1,1 = 0 c2,2 = 0 c3,3 = 0 c4,4 = 0
r0,0 = 0 r1,1 = 0 r2,2 = 0 r3,3 = 0 r4,4 = 0
if l=j-i 1 c0,1 = 8 c1,2 = 7 c2,3 = 3 c3,4 = 3
↓ r0,1 = 1 r1,2 = 2 r2,3 = 3 r3,4 = 4
2 c0,2 = 19 c1,3 = 12 c2,4 = 8
do int r0,2= 1 r1,3 = 2 r2,4 = 3
3 c0,3 = 25 C1,4 = 19
r0,3= 2 r1,4 = 2
while 4 c0,4 = 32
r0,4= 2

(a1, a2, a3, a4) = (do, if, int, while)

Optimal Binary Search Trees (OBST)
• Example
• Construct the optimal binary search tree for the following data: n = 4,
(a1, a2, a3, a4) = (end, goto, print, stop), with p(1) = 1/20, p(2) = 1/5,
p(3) = 1/10, p(4) = 1/20. q(0) = 1/5, q(1) = 1/10, q(2) = 1/5, q(3) =
1/20, q(4) = 1/20.
• Solution
• Computation of W, C and r has been carried out using the following
formulae.
• wi, i = qi
• ri. i = 0
• ci, i = 0
All Pair Shortest Path
• Let G =(V, E) be a directed graph.
• The all pairs shortest path problem is to determine the shortest path
between every pair of vertices in a directed graph G.
• That is, for every pair of vertices (i, j), we have to find a shortest path
from i to j as well as one from j to i.
All Pair Shortest Path
• Consider the following Graph.
• Objective: Find out the shortest path for each pair of vertices.
• Shortest Path by Considering a as Source
• a to b
• a to c
• a to d
• a to e
• Shortest Path by Considering b as Source
• b to a
• b to c
• b to d
• b to e
All Pair Shortest Path
• Shortest Path by Considering c as Source
• c to a
• c to b
• c to d
• c to e
• Shortest Path by Considering d as Source
• d to a
• d to b
• d to c
• d to e
All Pair Shortest Path
• Shortest Path by Considering e as Source
• e to a
• e to b
• e to c
• e to d
All Pair Shortest Path
• Let cost be the cost adjacency matrix for G such that
• cost[i, i] = 0, 1<= i <= n
• cost [i, j] = weight of the edge (i, j), if(i, j) ϵ E(G)
• cost [i, j] = ∞, if i ≠ j and (i, j) ! ϵ E(G)
All Pair Shortest Path
• The shortest i to j path in G, i ≠ j originates at vertex i and goes through
some intermediate vertices (possibly none) and terminates at vertex j.
• If k is an intermediate vertex on this shortest path, then the subpaths
from i to k and from k to j must be shortest paths from i to k and k to j,
respectively.
• Otherwise, the i to j path is not of minimum length.
• Therefore the principle of optimality holds.
• Let Ak (i, j) represent the length of a shortest path from i to j going
through no vertex of index greater than k, we obtain:
All Pair Shortest Path
• Algorithm All Paths (cost, A, n)
• // cost [1:n, 1:n] is the cost adjacency matrix of a graph with n vertices;
• //A [i, j] is the cost of a shortest path from vertex i to vertex j.
• //cost [i, i] = 0.0 for 1 < i < n
• {
• for i := 1 to n
• do for j:= 1 to n
• do A0 [i, j] := cost [i, j]; // copy cost into A.
• for k := 1 to n
• do for i := 1 to n
• do for j := 1 to n
• do Ak [i, j] := min {Ak-1 [i, j], (Ak-1 [i, k] + Ak-1 [k, j])};
• }
All Pair Shortest Path
All Pair Shortest Path
• Example
• Compute all pair shortest path for the following graph using Floyd’s
algorithm.
• Solution
4
• For the given graph n = 3
a b
• The cost matrix for the given graph is 11
6

2
0 4 11 3

cost = 6 0 2  c

3  0 
All Pair Shortest Path
4
• Copy the cost matrix to A0 a b
6
• for i = 1 to 3 11

• for j = 1 to 3 3 2

• A0 [i, j] = cost [i, j] c

0 4 11
0
= 6 0 2 
A  
3  0 
 4
All Pair Shortest Path a b
6
• for k := 1 to 3 11
• for i := 1 to 3 3 2

• for j := 1 to 3 c
• k= 1, i = 1, j = 1
• A 1 [1, 1] = min {(A0 [1, 1] + A0 [1, 1]), A0 [1, 1]} = min {0 0 4 11
+ 0, 0} = 0 0
= 6 0 2 
• k= 1, i = 1, j = 2
A  
3  0 
• A 1 [1, 2] = min {(A0 [1, 1] + A0 [1, 2]), A0 [1, 2]} = min
{(0 + 4), 4} = 4
0 4 11
• k= 1, i = 1, j = 3  
=
1
• A 1 [1, 3] = min {(A0 [1, 1] + A0 [1, 3]), A0 [1, 3]} = min A  
{(0 + 11), 11} = 11  
 4
All Pair Shortest Path a b
6
• k= 1, i = 2, j = 1 11
• A 1 [2, 1] = min {(A0 [2, 1] + A0 [1, 1]), A0 [2, 1]} = min {(6 + 0), 6} = 6 2
3
• k= 1, i = 2, j = 2
• A 1 [2, 2] = min {(A0 [2, 1] + A0 [1, 2]), A0 [2, 2]} = min {(6 + 4), 0)} = 0 c
• k= 1, i = 2, j = 3
• A 1 [2, 3] = min {(A0 [2, 1] + A0 [1, 3]), A0 [2, 3]} = min {(6 + 11), 2} = 2
• k= 1, i = 3, j = 1 0 4 11
• A 1 [3, 1] = min {(A0 [3, 1] + A0 [1, 1]), A0 [3, 1]} = min {(3 + 0), 3} = 3 0
= 6 0 2 
• k= 1, i = 3, j = 2
A  
• A 1 [3, 2] = min {(A0 [3, 1] + A0 [1, 2]), A0 [3, 2]} = min {(3 + 4), ∞} = 7
3  0 
• k= 1, i = 3, j = 3
• A 1 [3, 3] = min {(A0 [3, 1] + A0 [1, 3]), A0 [3, 3]} = min {(3 + 11), 0} = 0
0 4 11
1
= 6 0 2 
A  
3 7 0 
 4
All Pair Shortest Path a b
6
• for k := 1 to 3 11

• for i := 1 to 3 3 2

• for j := 1 to 3 c

• k= 2, i = 1, j = 1
0 4 11
• A 2 [1, 1] = min {(A1 [1, 2] + A1 [2, 1]), A1 [1, 1]} = min {4 6 0 2 
=
1
+ 6, 0} = 0 A  
• k= 2, i = 1, j = 2 3 7 0 
• A 2 [1, 2] = min {(A1 [1, 2] + A1 [2, 2]), A1 [1, 2]} = min
{(4 + 0), 4} = 4 0 4 6 
• k= 2, i = 1, j = 3 2
=  
A  
• A 2 [1, 3] = min {(A1 [1, 2] + A1 [2, 3]), A1 [1, 3]} = min  
{(4 + 2), 11} = 6
 4
All Pair Shortest Path a b
6
• k= 2, i = 2, j = 1 11
• A 2 [2, 1] = min {(A1 [2, 2] + A1[2, 1]), A1 [2, 1]} = min {(0 + 6), 6} = 6 2
3
• k= 2, i = 2, j = 2
• A 2 [2, 2] = min {(A1 [2, 2] + A1 [2, 2]), A1 [2, 2]} = min {(0 + 0), 0)} = 0 c
• k= 2, i = 2, j = 3
• A 2 [2, 3] = min {(A1 [2, 2] + A1 [2, 3]), A1 [2, 3]} = min {(0 + 2), 2} = 2 0 4 11
• k= 2, i = 3, j = 1 1
= 6 0 2 
• A 2 [3, 1] = min {(A1 [3, 2] + A1 [2, 1]), A1 [3, 1]} = min {(7 + 6), 3} = 3 A  
• k= 2, i = 3, j = 2 3 7 0 
• A 2 [3, 2] = min {(A1 [3, 2] + A1 [2, 2]), A1 [3, 2]} = min {(7 + 0), 7} = 7
• k= 2, i = 3, j = 3 0 4 6 
• A 2 [3, 3] = min {(A1 [3, 2] + A1 [2, 3]), A1 [3, 3]} = min {(7 + 2), 0} = 0 2
= 6 0 2 
A  
3 7 0
 4
All Pair Shortest Path a b
6
• for k := 1 to 3 11

• for i := 1 to 3 3 2

• for j := 1 to 3 c

• k= 3, i = 1, j = 1
• A 3 [1, 1] = min {(A2 [1, 3] + A2 [3, 1]), A2 [1, 1]} = min {6 0 4 6 
2
= 6 0 2 
+ 3, 0} = 0 A  
• k= 3, i = 1, j = 2 3 7 0
• A 3 [1, 2] = min {(A2 [1, 3] + A2 [3, 2]), A2 [1, 2]} = min
{(6 + 7), 4} = 4 0 4 6 
• k= 3, i = 1, j = 3 3
=  
A  
• A 3 [1, 3] = min {(A2 [1, 3] + A2 [3, 3]), A2 [1, 3]} = min  
{(6+ 0), 6} = 6
 4
All Pair Shortest Path a b
6
• k= 3, i = 2, j = 1 11
• A 3 [2, 1] = min {(A2 [2, 3] + A2[3, 1]), A2 [2, 1]} = min {(2 + 3), 6} = 5 2
3
• k= 3, i = 2, j = 2
• A 3 [2, 2] = min {(A2 [2, 3] + A2 [3, 2]), A2 [2, 2]} = min {(2 + 7), 0)} = 0 c
• k= 3, i = 2, j = 3
• A 3 [2, 3] = min {(A2 [2, 3] + A2 [3, 3]), A2 [2, 3]} = min {(2 + 0), 2} = 2 0 4 6 
• k= 3, i = 3, j = 1 2
= 6 0 2 
• A 3 [3, 1] = min {(A2 [3, 3] + A2 [3, 1]), A2 [3, 1]} = min {(0 + 3), 3} = 3 A  
• k= 3, i = 3, j = 2 3 7 0
• A 3 [3, 2] = min {(A2 [3, 3] + A2 [3, 2]), A2 [3, 2]} = min {(0 + 7), 7} = 7
• k= 3, i = 3, j = 3 0 4 6 
• A 3 [3, 3] = min {(A2 [3, 3] + A2 [3, 3]), A2 [3, 3]} = min {(0 + 0), 0} = 0 3
= 5 0 2 
A  
3 7 0
 4
All Pair Shortest Path a b
6
• k = 4 False 11
2
• The Algorithm will return A3 3
c
• The shortest path for each pair of vertices are

0 4 6 
5 0 2 
Vertex Pair Path cost /
=
3

a→b
length
A  
4
3 7 0
a→c 6
b→a 5
b→c 2
0 4 11
c→a 3 cost = 6 0 2 
c→b 7 3  0 