Module 4

Dynamic Programming

1
 Dynamic Programming
 Introduction to Dynamic Programming
 Three basic examples.
 The Knapsack Problem and Memory Functions
 Warshall’s Algorithm
 Floyd's Algorithm
 The Greedy Method
 Prim’s Algorithm,
 Kruskal’s Algorithm
 Dijkstra’s Algorithm
 Huffman Trees and Codes

2
 Dynamic Programming
 Dynamic programming design methods are used to solve the
problems with overlapping subproblems.
 These subproblems arise from a recurrence which relates solution of
the given problem to the solutions of its smaller subproblems.
 Instead of solving overlapping subproblems again and again,
dynamic programming help to solve each of the smaller
subproblems only once and record the results in a table from where
a solution to the original problem can be obtained.
 The Dynamic programming can also be used when the solution to a
problem can be viewed as the result of sequence of decisions.
 The term programming refers to plans, not programming.
 The Dynamic programming was invented by Richard Bellman of US,
in 1950s as a general method for optimizing multistage decision
processes.

3
 Dynamic Programming
 There are two variations of dynamic programming such as Bottom-up
and top-down approaches.
 In both the methods, the crucial step of deriving a recurrence that
relates to a solution of the problem to the solutions of its smaller
subproblems remains same.
 The Dynamic programming is mostly used to solve optimization
problems.
 Most of dynamic programming applications that deal with optimization
problems are based on the principle of optimality.
 It says that an optimal solution to any instance of an optimization
problem is composed of optimal solutions to its sub-instances.

4
 Dynamic Programming
Example-1: Generating the Fibonacci numbers.

 The Fibonacci numbers are the elements of the sequence 0, 1, 1, 2, 3, 5,

8, 13, 21, 34, . . . , which is defined by the simple recurrence,
F(n) = F(n-1) + F(n-2) for n > 1, with two initial conditions F(0) = 0, F(1) = 1.
 Using the above recurrence, we can directly compute the nth Fibonacci
number F(n).
 Here, the problem of computing F(n) is expressed in terms of its smaller
and overlapping subproblems of computing F(n-1) and F(n-2).
 So, we can simply fill the elements of a one-dimensional array with n+1
consecutive values of F(n) by starting with 0 and 1(initial conditions) and
using above recurrence as the rule to generate all the other elements.

5
 Three Basic Examples
EXAMPLE 1: Coin-row problem:
 There is a row of n coins whose values are some positive integers c1, c2,
. . . , cn which need not be distinct.
 The goal is to pick up the maximum amount of money subject to the
constraint that no two coins adjacent in the initial row can be picked up.
 Let F(n) be the maximum amount that can be picked up from the row of
n coins.
 To derive a recurrence for F(n), we partition all the allowed coin
selections into two groups: those that include the last coin and those
without it.
 The largest amount we can get from the first group is equal to cn+F(n-2),
the value of the nth coin plus the maximum amount we can pick up from
the first n-2 coins.
 The maximum amount we can get from the second group is equal to
F(n-1) by the definition of F(n).
6
 Three Basic Examples
 Thus, we have the following recurrence subject to the initial conditions:
F(n) = max{cn + F(n-2), F(n-1)} for n > 1, Eq. (8.3)
F(0) = 0, F(1) = c1.
 We can compute F(n) by filling the one-row table from left to right.

7
 Three Basic Examples
 Application of algorithm to the coin row of denominations 5, 1, 2, 10, 6, 2 is
shown in Figure 8.1.
 It yields the maximum amount of 17.
 Note that, we also solved the problem for the first i coins in the row given for
every 1≤ i ≤ 6.
 For example, for i = 3, the maximum amount is F(3) = 7.
 To find the coins with the maximum total value found, we need to backtrace
the computations to see which of the two possibilities, cn + F(n-2) or F(n-1)
produced the maximum.
 In the last application of the formula, the sum c6+F(4) produced maximum,
which means that the coin c6 = 2 is a part of an optimal solution.
 In computing F(4), the maximum was produced by the sum c4 + F(2), which
means that the coin c4 = 10 is also a part of an optimal solution.

8
 Three Basic Examples
 Finally, in computing F(2), the maximum was produced by F(1), which
implies that the coin c2 is not the part of an optimal solution but the coin
c1 = 5 is part of an optimal solution.
 Thus, the optimal solution is {c1, c4, c6}.
 To avoid repeated computations during the backtracing, the information
about which of the two terms in the formula was larger can be recorded
in an extra array when the values of F are computed.
 Using the CoinRow to find F(n), the largest amount of money that can
be picked up and the coins composing an optimal set takes (n) time
and (n) space.

9
Three Basic Examples

10
 Three Basic Examples
EXAMPLE 2: Change-making problem:
 The general instance of the problem is to give change for amount n
using the minimum number of coins of denominations d1< d2< . . .< dm.
 We assume the availability of unlimited quantities of coins for each of
the m denominations d1< d2< . . .< dm where d1 = 1.
 Let F(n) be the minimum number of coins whose value is equal to n, and
F(0) = 0.
 The amount n can be obtained by adding one coin of denomination dj to
the amount n - dj for j = 1, 2, . . . , m such that n ≥ dj.
 Therefore, we can consider all such denominations and select the one
minimizing F(n - dj) + 1.
 Since 1 is a constant, we can find the smallest F(n - dj) first and then
add 1 to it.

11
 Three Basic Examples
 Hence, we have the following recurrence for F(n).

F(n) = min {F(n- 𝑗)} + 1 for n > 0, Eq. (8.4)

𝑗: 𝑛 ≥ 𝑑𝑗
F(0) = 0

 We compute F(n) by filling a one-row table from left to right similar to the
coin-row problem, but computing a table entry here requires finding the
minimum of up to m numbers.

12
Three Basic Examples

13
 Three Basic Examples
 Application of the algorithm for amount n = 6 and the denominations
1, 3, 4 is shown in Figure 8.2.
 The answer it produce is two coins.
 The time and space efficiencies of the algorithm are O(nm) and (n)
respectively.
 To find the coins of an optimal solution, we need to backtrace the
computations to see which denominations have produced the
minimum value in formula (8.4).
 For the given problem instance, the last application of the formula
(for n = 6), the minimum was produced by d2 = 3.
 The second minimum (for n = 6 - 3) was also produced for a coin of
that denomination.
 Thus, the minimum-coin set for n = 6 is obtained by two coins of
denomination 3.

14
Three Basic Examples

15
 Three Basic Examples
EXAMPLE 3: Coin-collecting problem:
 Several coins are placed in the cells of an n × m board, and no more
than one coin per cell.
 A robot, located in the upper left cell of the board, needs to collect as
many of the coins as possible and bring them to the bottom right cell.
 On each step, the robot can move either one cell to the right or one
cell down from its current location.
 When the robot visits a cell with a coin, it always picks up that coin.
 We have to design an algorithm to find the maximum number of
coins the robot can collect and a path it needs to follow to do this.
 Let F(i, j) be the largest number of coins the robot can collect and
bring to the cell(i, j) in the ith row and jth column of the board.
 It can reach this cell either from the adjacent cell(i-1, j) above it or
from the adjacent cell(i, j-1) to the left of it.

16
 Three Basic Examples
 The largest numbers of coins that can be brought to these cells are F(i-1, j)
and F(i, j-1) respectively.
 Remember that there are no adjacent cells above the cells in the first row,
and there are no adjacent cells to the left of the cells in the first column.
 For those cells, we assume that F(i-1, j) and F(i, j-1) are equal to 0 for their
nonexistent neighbors.
 So, the largest number of coins the robot can bring to cell(i, j) is the
maximum of these two numbers plus one possible coin at cell(i, j) itself.
 In other words, we have the following formula for F(i, j):

F(i, j) = max{F(i-1 ), F(i -1)} + cij for 1 i n, 1 j m Eq. (8.5)

F(0, j) = 0 for 1 j m and F(i, 0) = 0 for 1 i n

 If there is a coin in cell(i, j), then cij = 1 otherwise cij = 0.

17
 Three Basic Examples
 Using these formulas, we can fill in the n × m table of F(i, j) values
either row by row or column by column.

18
 Three Basic Examples
 Figure 8.3b illustrate the algorithm for the coin setup of Figure 8.3a.
 By tracing the computations backward, we can get an optimal path.
 If F(i-1, j) > F(i, j-1), an optimal path to cell(i, j) must come down from the
adjacent cell above it.
 If F(i-1, j) < F(i, j-1), an optimal path to cell(i, j) must come from the
adjacent cell on the left.
 If F(i-1, j) = F(i, j-1), it can reach cell(i, j) from either direction.
 This yields two optimal paths for the instance in Figure 8.3a as shown in
Figure 8.3c.
 If ties are ignored, one optimal path can be obtained in (n + m) time.
 Since computing the value of F(i, j) by formula (8.5) for each cell of the
table takes constant time, the time efficiency of the algorithm is (nm).
 Its space efficiency is also (nm).

19
Three Basic Examples

20
 Knapsack problem using DP
 For a given a set of n items with weights w1, . . . , wn and the values or
profits v1, . . . ,vn and a knapsack capacity of W, we must find the most
valuable subset of items that fit into the knapsack.
 To design a dynamic programming algorithm, we have to derive a
recurrence relation that expresses a solution in terms of its smaller
subinstances.
 Consider the problem instance defined by the first i items, 1≤ i ≤ n,
with the weights w1, . . . , wi, and values v1, . . .,vi, and the knapsack
capacity j, 1 ≤ j ≤ W.
 Let F(i, j) be the value of an optimal solution of this problem instance,
which corresponds to the profit of the most valuable subset of the first i
items that fit into the knapsack capacity of j.

21
 Knapsack problem using DP
 We can divide all the subsets of the first i items that fit the knapsack
capacity of j into two categories:
1. those that do not include the ith item,
2. and those include the ith item.
 For the subsets that do not include the ith item, the value of an optimal
subset is given by,
F(i, j) = F(i-1, j).
 For the subsets that include the ith item (j-wi ≥ 0), an optimal subset will
include this item and an optimal subset of the first (i-1) items that fits
into the knapsack of capacity of j-wi.
 The value of such an optimal subset is given by,
F(i, j) = vi + F(i-1, j-wi).
 Therefore, the optimal solution among all feasible subsets of the first i
items is the maximum of these two values.
22
 Knapsack problem using DP
 If the ith item does not fit into the knapsack, the value of an optimal
subset selected from the first i items is same as the value of an
optimal subset selected from the first i-1 items.
 Hence, we get the following recurrence.
F(i−1, j), vi + F(i−1, j−wi)} j−wi ≥ 0 Eq. 8.6
F(i, j) = F(i−1, j) j−wi < 0

 The initial conditions are defined as follows:

F(0, j) = 0 for j ≥ 0 and F(i, 0) = 0 for i ≥ 0.
 Our goal is to find F(n, W), the maximum value of a subset of n items
that fit into the knapsack capacity of W and an optimal subset itself.

23
 Knapsack problem using DP
 The following figure illustrates the values involved in the above equations.
 For i, j > 0, to compute the entry in the ith row and jth column F(i, j), we
compute the maximum of the entry in the previous row and the same
column and the sum of vi and the entry in the previous row and wi
columns to the left.
 The table can be filled either row by row or column by column.

24
 Knapsack problem using DP
Example-1:

The dynamic programming table filled by applying the formulas.

25
 Knapsack problem using DP
 The maximal value is F(4, 5) = $37.
 We can find the items of an optimal subset by backtracking the
computations of this entry in the table.
 Since F(4, 5) > F(3, 5), item 4 has to be included in an optimal
solution along with an optimal subset for filling the remaining 5-2 = 3
units of the knapsack capacity.
 The value of the latter is F(3, 3).
 Since F(3, 3) = F(2, 3), item 3 need not be in an optimal subset.
 Since F(2, 3) > F(1, 3), item 2 is a part of an optimal selection along
with an optimal subset for filling the remaining 3-1 = 2 units of the
knapsack capacity.
 Similarly, since F(1, 2) > F(0, 2), item 1 is included in the optimal
solution.
 Therefore, optimal solution is given by {item 1,item 2, item 4}.
26
 Algorithm
Algorithm DPKNAPSACK (F, W, M)
// Description: Solve binary knapsack problem using dynamic programming
// Input: Set of items n, set of weight W, profit of items F and knapsack
capacity M
// Output: Array F, which holds the solution of problem

for j ← 0 to M
F[0, j] ← 0
for i ← 1 to n
F[i, 0] ← 0
for i ← 1 to n
for j ← 0 to M
if wi ≤ j // item i can be part of the solution
if vi + F[i-1, j-wi] > F[i-1, j]
F[i, j] ← vi + F[i-1, j-wi]
else
F[i, j] ← F[i-1, j]
else // wi > j
F[i, j] ← F[i-1, j]
27
 Analysis
 The time efficiency and space efficiency of this algorithm are both
in (nW).
 The time needed to find the composition of an optimal solution is
in O(n).

Home Work:
1. Find an optimal solution for following 0/1 Knapsack problem using
dynamic programming.
n = 4, W = 5, (w1, w2, w3, w4) = (2, 3, 4, 5) and
(p1, p2, p3, p4) = (3, 4, 5, 6).

28
 Memory Functions
 The direct top-down approach to find a solution to the recurrence
leads to an algorithm that solves common subproblems more than
once, and hence is very inefficient.
 The classic dynamic programming approach works bottom up where it
fills a table with solutions to all smaller subproblems, but each of them
is solved only once.
 An unsatisfying aspect of this approach is that solutions to some of
these smaller subproblems are often not necessary for getting a
solution to the original problem.
 Since this drawback is not present in the top-down approach, it is
natural to try to combine the strengths of the top-down and bottom-
up approaches.
 The goal is to get a method that solves only the subproblems that are
necessary and does so only once.
 Such a method exists which is based on using memory functions.
29
Algorithm

30
Example

31
 Warshall’s and Floyd’s Algorithms
 Warshall’s algorithm is used to compute the transitive closure of a
directed graph and the Floyd’s algorithm is used to solve the all-pairs
shortest-paths problem.
 Both algorithms are developed to derive a relationship between the
problem and its simpler or smaller version.

Adjacency matrix :
 The adjacency matrix A = {aij} of a directed graph is a boolean matrix
that has 1 in its ith row and jth column if and only if there is a directed
edge from ith vertex to jth vertex.

32
 Warshall’s and Floyd’s Algorithms
Transitive closure :
 The transitive closure of a directed graph with n vertices is defined
as n x n boolean matrix T = {tij }, in which the element in the ith row
and the jth column is 1 if there exists a nontrivial path (i.e., directed
path of a positive length) from ith vertex to jth vertex, otherwise tij is 0.

Example:

33
 Transitive Closure
 We can generate the transitive closure of a digraph using depth-
first search or breadth-first search.
 But, as these methods traverses the same digraph several times, we
use Warshall's algorithm (named after Stephen Warshall) which
perform better.
 Warshall's algorithm constructs the transitive closure through a
series of n × n boolean matrices(bit matrices).
R(0), R(1), . . . , R(k-1), R(k), . . . , R(n)
 Each of these matrices provides some information about the directed
paths in the digraph.

34
 Warshall’s Algorithm
 The element rij(k) in the ith row and jth column of matrix R(k) (i, j = 1, 2, . . . , n,
k = 0, 1, . . . , n) is equal to 1 if and only if there exists a directed path of a
positive length from ith vertex to jth vertex with each intermediate vertex (if
any) numbered not higher than k.
 Thus, the series starts with R(0), which does not allow any intermediate
vertices in its paths and hence, R(0) is same as the adjacency matrix of the
digraph.
 R(1) contains the information about paths that can use the first vertex as
intermediate and hence it may contain more 1’s than R(0).
 In general, each subsequent matrix in the series will have one more
vertex to use as intermediate for its paths than its predecessor, and may
contain more 1’s.
 The last matrix in the series R(n) reflects paths that can use all n vertices
of the digraph as intermediate and hence it represents transitive closure
of the digraph.
35
 Warshall’s Algorithm
 Note that we compute all the elements of each matrix R(k) from its immediate
predecessor R(k-1) in the series.
 Let rij(k) be equal to 1, which correspond to the element in the ith row and jth
column of matrix R(k).
 It means that there exists a path from ith vertex vi to jth vertex vj with each
intermediate vertex numbered not higher than k.
 So, the path contains,
vi, a list of intermediate vertices each numbered not higher than k, vj.
 Two situations regarding this path are possible.
 In the first, the list of its intermediate vertices does not contain kth vertex vk.
 Then, the path from vi to vj has intermediate vertices numbered not higher
than k-1, and therefore rij(k-1) is also equal to 1.

36
 Warshall’s Algorithm
 The second possibility is that path from vi to vj contain kth vertex vk among the
intermediate vertices.
 We may assume that the vertex vk occurs only once in that list.
 If it is not the case, we can create a new path from vi to vj with this property
by simply eliminating all the vertices between the first and last occurrences
of vk in it.
 Hence, the path from vi to vj can be rewritten as follows:
vi, vertices numbered ≤ k-1, vk, vertices numbered ≤ k-1, vj.
 The first part in the above representation means that there exists a path
from vi to vk with each intermediate vertex numbered not higher than k-1
(hence, rik(k-1) = 1), and the second part means that there exists a path from
vk to vj with each intermediate vertex numbered not higher than k-1 (hence,
rkj(k-1) = 1).
 That is, if rij(k) = 1, then either rij(k-1) = 1 or both rik(k-1) = 1 and rkj(k-1) = 1.
 Note that the converse of this assertion is also true.
37
 Warshall’s Algorithm
 Hence, we have the following formula to generate the elements of
matrix R(k) from the elements of matrix R(k-1):
rij(k) = rij(k-1) or (rik(k-1) AND rkj(k-1)).
 The above formula is at the heart of Warshall’s algorithm.
 This formula implies the following rule to generate the elements of
matrix R(k) from the elements of matrix R(k-1).
 If an element rij is 1 in R(k-1), it remains 1 in R(k).
 If an element rij is 0 in R(k-1), it must be changed to 1 in R(k) if and only
if the element in its ith row and kth column and the element in its kth
row and jth column are both 1’s in R(k-1).

38
 Warshall’s Algorithm
 This rule for changing 0’s to 1’s in Warshall’s algorithm is shown below.

39
 Example

Note: New 1’s are in bold.

40
 Example

Note: New 1’s are in bold.

41
 Warshall’s Algorithm
Simple steps:

1. Write the adjacency matrix for the given digraph.

2. Select 1st row and 1st column of a matrix.
3. For each row and column compute
R(k)[i, j] = R(k-1)[i, j] or {R(k-1)[i, k] AND R(k-1)[k, j] }
4. Update the new value in a matrix.
5. Repeat the process for all rows and columns of the matrix.

42
 Example
1. Consider the digraph.
a b c d
a 0 1 0 0
R(0) = b 0 0 0 1
c 0 0 0 0
d 1 0 1 0
Adjacency matrix
Select 1st row and 1st column:
a b c d
a b c d
a 0 1 0 0
a 0 1 0 0
b 0 0 0 1
R(1) = b 0 0 0 1
c 0 0 0 0
c 0 0 0 0
d 1 1 1 0
d 1 0 1 0
Updated new value
Since, (d, a)=1 and (a, b)=1, (d, b)=1
43
 Example
Select 2nd row and 2nd column:

a b c d
a 0 1 0 0
R(1) = b 0 0 0 1
c 0 0 0 0
d 1 1 1 0
Since,
(a, b)=1 and (b, d)=1, (a, d)=1
(d, b)=1 and (b, d)=1, (d, d)=1 a b c d
a 0 1 0 1
b 0 0 0 1
R(2) = c 0 0 0 0
d 1 1 1 1

Updated new values

44
 Example
Select 3rd row and 3rd column:
a b c d
a 0 1 0 1
R(2) = b 0 0 0 1
c 0 0 0 0
d 1 1 1 1
Since,
(d, c)=1 and no 1’s in the 3rd row, we have
a b c d
a 0 1 0 1
b 0 0 0 1
R(3) = c 0 0 0 0
d 1 1 1 1

No updating is required
45
 Example
Select 4th row and 4th column:
a b c d
a 0 1 0 1
b 0 0 0 1
R(3) =
Since, c 0 0 0 0
(a, d)=1 and (d, a)=1, (a, a)=1 d 1 1 1 1
(a, d)=1 and (d, b)=1, (a, b)=1
(a, d)=1 and (d, c)=1, (a, c)=1
(a, d)=1 and (d, d)=1, (a, d)=1 a b c d
(b, d)=1 and (d, a)=1, (b, a)=1 a 1 1 1 1
(b, d)=1 and (d, b)=1, (b, b)=1 b 1 1 1 1
(b, d)=1 and (d, c)=1, (b, c)=1 R(4) = c 0 0 0 0
(b, d)=1 and (d, d)=1, (b, d)=1 d 1 1 1 1
(d, d)=1 and (d, a)=1, (d, a)=1
(d, d)=1 and (d, b)=1, (d, b)=1
(d, d)=1 and (d, c)=1, (d, c)=1 Updated new values
(d, d)=1 and (d, d)=1, (d, d)=1 46
Algorithm

47
 Analysis
 The basic operation lies inside the innermost for loop.
 The time complexity is calculated as shown below.
T(n) =
T(n) = −1+1 Upper bound - Lower bound + 1
T(n) =
T(n) = n
T(n) = n -1+1 Upper bound - Lower bound + 1
T(n) = n
T(n) = n2
T(n) = n2 −1+1 Upper bound - Lower bound + 1
T(n) = n3
 Therefore, the time efficiency of Warshall’s algorithm is (n3).
48
 Analysis
 We can make the algorithm to run faster by treating matrix rows as
bit strings and employ the bitwise OR operation available in most of
the modern computer languages.
Space efficiency:
 Though separate matrices to record intermediate results of the
algorithm are used, we can avoid this.

49
 Home Work
1. Apply Warshall's Algorithm to compute transitive closure for
the following directed graph.

2. Apply Warshall's Algorithm to compute transitive closure for

the following directed graph.

50
 Home Work
3. Apply Warshall's Algorithm to compute transitive closure for
the directed graph defined by the following adjacency matrix.
a b c d
a
b
c
d

51
 All Pairs Shortest Paths
Definition:
 For the given weighted connected graph (directed or undirected), the
problem of all-pairs shortest paths is to find the distances from each
vertex to all other vertices.
 In other words, it finds the lengths of shortest paths from each vertex to
all other vertices.

Applications:
 Communications, transportation networks, and operations research.
 Pre-computing distances for motion planning in computer games.

52
 All Pairs Shortest Paths
 In this problem, we record the lengths of shortest paths in an n × n
matrix called distance matrix denoted by D, where the element dij in
the ith row and jth column of the matrix indicate the length of shortest
path from ith vertex to jth vertex.
 Floyd’s algorithm (named after Robert W. Floyd) is used to generate
distance matrix.

Example:

(a) Digraph. (b) Its weight matrix. (c) Its distance matrix

53
 Floyds Algorithm
 Floyd’s algorithm computes the distance matrix of a weighted graph with
n vertices through a series of n × n matrices, D(0), D(1),..., D(k-1), D(k), ..., D(n).
 Each of these matrices contains the lengths of shortest paths with some
constraints on the paths considered for the matrix.
 The element dij(k) in the ith row and the jth column of matrix D(k) (i, j = 1, 2,
. . . , n, k = 0, 1, . . . , n) indicate the length of the shortest path among all
paths from ith vertex to jth vertex with each intermediate vertex(if any),
numbered not higher than k.
 The series starts with D(0) which does not allow any intermediate vertices
in its paths.
 Hence, D(0) is same as the weight matrix of the graph.
 The last matrix in the series D(n) contains the lengths of the shortest
paths among all paths that can use all n vertices as intermediate.
 D(n) represent the final distance matrix.

54
 Floyds Algorithm
 Like Warshall’s algorithm, we compute the elements of each matrix
D(k) from its immediate predecessor D(k-1) in the series.
 Let dij(k) be the element in the ith row and the jth column of matrix D(k).
 This means that dij(k) is equal to the length of the shortest path
among all paths from the ith vertex vi to the jth vertex vj with their
intermediate vertices numbered not higher than k.
vi, a list of intermediate vertices each numbered not higher than k, vj.
 We can partition all such paths into two disjoint subsets, one that do
not use the kth vertex vk as intermediate and the other use the kth
vertex vk as intermediate.
 Since the paths of the first subset have their intermediate vertices
numbered not higher than k-1, the shortest length of them is dij(k-1).

55
 Floyds Algorithm
 All paths in the second subset that use vertex vk as their intermediate
vertex exactly once have the following form:
vi, vertices numbered ≤ k-1, vk, vertices numbered ≤ k-1, vj.
 In other words, every path in the subset is made up of a path from vi
to vk with each intermediate vertex numbered not higher than k-1 and
a path from vk to vj with each intermediate vertex numbered not
higher than k-1.
 This situation is symbolically shown below.

56
 Floyds Algorithm
 Since the length of the shortest path from vi to vk among the paths
that use intermediate vertices numbered not higher than k-1 is equal
to dik(k-1) and the length of the shortest path from vk to vj among the
paths that use intermediate vertices numbered not higher than k-1 is
equal to dkj(k-1), the length of the shortest path among the paths that
use kth vertex as the intermediate vertex is equal to dik(k-1) + dkj(k-1).
 By considering the lengths of the shortest paths in both subsets we
get the following recurrence:
dij(k) = min{dij(k-1), dik(k-1) + dkj(k-1)} for k ≥ 1, dij(0) = wij.

 That is, the element in ith row and jth column of the current distance
matrix D(k-1) is replaced by the sum of the elements in the same ith row
and the kth column and in the same kth row and jth column if and only if
the sum is smaller than its current value.

57
 Example

Updated elements are shown in bold. 58

 Floyds Algorithm

 The time efficiency of Floyd’s algorithm is (n3), which is same

as Warshall's algorithm.
59