COMP90038 Algorithms and Complexity
COMP90038
Algorithms and Complexity
Lecture 19: Warshall and Floyd
(with thanks to Harald Søndergaard & Michael Kirley)
Andres Munoz-Acosta
munoz.m@unimelb.edu.au
Peter Hall Building G.83
mailto:munoz.m@unimelb.edu.au
Recap
• Dynamic programming is a bottom-up problem solving technique. The idea
is to divide the problem into smaller, overlapping ones. The results are
tabulated and used to find the complete solution.
• Solutions often involves recursion.
• Dynamic programming is often used on Combinatorial Optimization
problems.
• We are trying to find the best possible combination subject to some constraints
• Two classic problems
• Coin row problem
• Knapsack problem
The coin row problem
• You are shown a group of coins of different denominations ordered in a
row.
• You can keep some of them, as long as you do not pick two adjacent ones.
• Your objective is to maximize your profit , i.e., you want to take the largest amount
of money.
• The solution can be expressed as the recurrence:
The coin row problem
• Let’s quickly examine each step for [20 10 20 50 20
10 20]:
• S[0] = 0
• S[1] = 20
• S[2] = max(S[1] = 20, S[0] + 10 = 0 + 10) = 20
• S[3] = max(S[2] = 20, S[1] + 20 = 20 + 20 = 40) = 40
• S[4] = max(S[3] = 40, S[2] + 50 = 20 + 50 = 70) = 70
• S[5] = max(S[4] = 70, S[3] + 20 = 40 + 20 = 60) = 70
• S[6] = max(S[5] = 70, S[4] + 10 = 70 + 10 = 80) = 80
• S[7] = max(S[6] = 80, S[5] + 20 = 70 + 20 = 90) = 90
1 2 3 4 5 6 7
0 20 10 20 50 20 10 20
STEP 0 0
STEP 1 0 20
STEP 2 0 20 20
STEP 3 0 20 20 40
STEP 4 0 20 20 40 70
STEP 5 0 20 20 40 70 70
STEP 6 0 20 20 40 70 70 80
STEP 7 0 20 20 40 70 70 80 90
SOLUTION
1 1 1 1 1 1 1
3 4 4 4 4
6 7
The knapsack problem
• We also talked about the knapsack
problem:
• Given a list of n items with:
• Weights {w1, w2, …, wn}
• Values {v1, v2, …, vn}
• and a knapsack (container) of capacity W
• Find the combination of items with the
highest value that would fit into the
knapsack
• All values are positive integers
The knapsack problem
• The critical step is to find a good answer to the question: what is the smallest
version of the problem that I could solve first?
• Imagine that I have a knapsack of capacity 1, and an item of weight 2. Does it fit?
• What if the capacity was 2 and the weight 1. Does it fit? Do I have capacity left?
• Given that we have two variables, the recurrence relation is formulated over two
parameters:
• the sequence of items considered so far {1, 2, … i}, and
• the remaining capacity w ≤ W.
• Let K(i,w) be the value of the best choice of items amongst the first i using
knapsack capacity w.
• Then we are after K(n,W).
The knapsack problem
• By focusing on K(i,w) we can express a recursive solution.
• Once a new item i arrives, we can either pick it or not.
• Excluding i means that the solution is K(i-1,w), that is, which items were
selected before i arrived with the same knapsack capacity.
• Including i means that the solution also includes the subset of previous items
that will fit into a bag of capacity w-wi ≥ 0, i.e., K(i-1,w-wi) + vi.
The knapsack problem
• This was expressed as a recursive function, with a base state:
• And a general case:
• Our example was:
• The knapsack capacity W = 8
• The values are {42, 12, 40, 25}
• The weights are {7, 3, 4, 5}
The knapsack problem
• Did you complete the table? j 0 1 2 3 4 5 6 7 8
v w i
0 0 0 0 0 0 0 0 0 0
42 7 1 0 0 0 0 0 0 0 42 42
12 3 2 0 0 0 12 12 12 12 42 42
40 4 3 0 0 0 12 40 40 40 52 52
25 5 4 0 0 0 12 40 40 40 52 52
Solving the Knapsack Problem with Memoing
• To some extent the bottom-up (table-filling) solution is overkill:
• It finds the solution to every conceivable sub-instance, most of which are
unnecessary
• In this situation, a top-down approach, with memoing, is preferable.
• There are many implementations of the memo table.
• We will examine a simple array type implementation.
The knapsack problem
• Lets look at this algorithm, step-
by-step
• The data is:
• The knapsack capacity W = 8
• The values are {42, 12, 40, 25}
• The weights are {7, 3, 4, 5}
• F is initialized to all -1, with the
exceptions of i=0 and j=0, which
are initialized to 0.
The knapsack problem
• We start with i=4 and j=8 j 0 1 2 3 4 5 6 7 8
v w i
0 0 0 0 0 0 0 0 0 0
42 7 1 0 -1 -1 -1 -1 -1 -1 -1 -1
12 3 2 0 -1 -1 -1 -1 -1 -1 -1 -1
40 4 3 0 -1 -1 -1 -1 -1 -1 -1 -1
25 5 4 0 -1 -1 -1 -1 -1 -1 -1 -1
• i = 4
• j = 8
• K[4-1,8] = K[3,8]
• K[4-1,8-5] + 25 = K[3,3] + 25
The knapsack problem
• Next is i=3 and j=8 j 0 1 2 3 4 5 6 7 8
v w i
0 0 0 0 0 0 0 0 0 0
42 7 1 0 -1 -1 -1 -1 -1 -1 -1 -1
12 3 2 0 -1 -1 -1 -1 -1 -1 -1 -1
40 4 3 0 -1 -1 -1 -1 -1 -1 -1 -1
25 5 4 0 -1 -1 -1 -1 -1 -1 -1 -1
• i = 3
• j = 8
• K[3-1,8] = K[2,8]
• K[3-1,8-4] + 40 = K[2,4] + 40
The knapsack problem
• Next is i=2 and j=8 j 0 1 2 3 4 5 6 7 8
v w i
0 0 0 0 0 0 0 0 0 0
42 7 1 0 -1 -1 -1 -1 -1 -1 -1 -1
12 3 2 0 -1 -1 -1 -1 -1 -1 -1 -1
40 4 3 0 -1 -1 -1 -1 -1 -1 -1 -1
25 5 4 0 -1 -1 -1 -1 -1 -1 -1 -1
• i = 2
• j = 8
• K[2-1,8] = K[1,8]
• K[2-1,8-3] + 12 = K[1,5] + 12
The knapsack problem
• Next is i=1 and j=8
• Here we reach the bottom of
this recursion
j 0 1 2 3 4 5 6 7 8
v w i
0 0 0 0 0 0 0 0 0 0
42 7 1 0 -1 -1 -1 -1 -1 -1 -1 42
12 3 2 0 -1 -1 -1 -1 -1 -1 -1 -1
40 4 3 0 -1 -1 -1 -1 -1 -1 -1 -1
25 5 4 0 -1 -1 -1 -1 -1 -1 -1 -1
• i = 1
• j = 8
• K[1-1,8] = K[0,8] = 0
• K[1-1,8-7] + 42 = K[0,1] + 42 = 0 + 42 = 42
The knapsack problem
• Next is i=1 and j=5.
• As before, we also reach the
bottom of this branch.
j 0 1 2 3 4 5 6 7 8
v w i
0 0 0 0 0 0 0 0 0 0
42 7 1 0 -1 -1 -1 -1 0 -1 -1 42
12 3 2 0 -1 -1 -1 -1 -1 -1 -1 -1
40 4 3 0 -1 -1 -1 -1 -1 -1 -1 -1
25 5 4 0 -1 -1 -1 -1 -1 -1 -1 -1
• i = 1
• j = 5
• K[1-1,5] = K[0,5] = 0
• j – w[1] = 5-8 < 1 → return 0 The knapsack problem • We can trace the complete algorithm, until we find our solution. • The states visited (18) are shown in the table. • In the bottom-up approach we visited all the states (40). • Given that there are a lot of places in the table never used, the algorithm is less space-efficient. • You may use a hash table to improve space efficiency. i j value 0 8 0 0 1 0 1 8 42 0 5 0 1 5 0 2 8 42 0 4 0 1 4 0 0 1 0 1 1 0 2 4 12 3 8 52 0 3 0 1 3 0 1 0 0 2 3 12 3 3 12 4 8 52 A practice challenge • Can you solve the problem in the figure? • W = 15 • w = [1 1 2 4 12] • v = [1 2 2 10 4] • Because it is a larger instance, memoing is preferable. • How many states do we need to evaluate? • FYI the answer is $15 {1,2,3,4} Dynamic Programming and Graphs • We now apply dynamic programming to two graph problems: • Computing the transitive closure of a directed graph; and • Finding shortest distances in weighted directed graphs. Warshall’s algorithm • Warshall's algorithm computes the transitive closure of a directed graph. • An edge (a,d) is in the transitive closure of graph G iff there is a path in G from a to d. • Transitive closure is important in applications where we need to reach a “goal state” from some “initial state”. • Warshall's algorithm was not originally thought of as an instance of dynamic programming, but it fits the bill a b c d Warshall’s algorithm • Warshall's algorithm computes the transitive closure of a directed graph. • An edge (a,d) is in the transitive closure of graph G iff there is a path in G from a to d. • Transitive closure is important in applications where we need to reach a “goal state” from some “initial state”. • Warshall's algorithm was not originally thought of as an instance of dynamic programming, but it fits the bill a b c d Warshall’s Algorithm • Assume the nodes of graph G are numbered from 1 to n. • Is there a path from node i to node j using nodes [1 … k] as “stepping stones”? • Such path will exist if and only if we can: • step from i to j using only nodes [1 … k-1], or • step from i to k using only nodes [1 … k-1], and then step from k to j using only nodes [1 … k-1]. Warshall’s Algorithm • If G’s adjacency matrix is A then we can express the recurrence relation as: • This gives us a dynamic programming algorithm: Warshall’s Algorithm • If we allow input A to be used for the output, we can simplify things. • If R[i,k,k-1] (that is, A[i,k]) is 0 then the assignment is doing nothing. • But if A[i,k] is 1 and if A[k,j] is also 1, then A[i,j] gets set to 1. • But now we notice that A[i,k] does not depend on j, so testing it can be moved outside the innermost loop. Warshall’s Algorithm • This leads to a simpler version of the algorithm. • If each row in the matrix is represented as a bit-string, then the innermost for loop (and j) can be gotten rid of – instead of iterating, just apply the “bitwise or” of row k to row i. Warshall’s Algorithm • Let’s examine this algorithm. Let our graph be. • Then, the adjacency matrix is: 1 2 5 3 47 6 Warshall’s Algorithm • For k=1, all the elements in the column are zero, so this if statement does nothing. Warshall’s Algorithm • For k=2, we have A[1,2] = 1 and A[5,2] = 1, and A[2,3]=1 Warshall’s Algorithm • For k=2, we have A[1,2] = 1 and A[5,2] = 1, and A[2,3]=1 • Then, we can make A[1,3] = 1 and A[5,3] = 1 Warshall’s Algorithm • For k=3, we have A[1,3], A[2,3], A[4,3], A[5,3], A[3,6] and A[3,7] equal to 1 Warshall’s Algorithm • For k=3, we have A[1,3], A[2,3], A[4,3], A[5,3], A[3,6] and A[3,7] equal to 1 • Then, we can make A[1,6], A[2,6], A[4,6], A[1,7], A[2,7], A[4,7], and A[5,7] equal to 1. Warshall’s algorithm • Let’s look at the final steps: k=3 Warshall’s algorithm • Let’s look at the final steps: k=3 k=4 Warshall’s algorithm • Let’s look at the final steps: • At k=5 and k=7, there is no changes to the matrix. k=3 k=4 k=6 Warshall’s algorithm • Warshall's algorithm’s complexity is Θ(n3). There is no difference between the best, average, and worst cases. • The algorithm has an incredibly tight inner loop, making it ideal for dense graphs. • However, it is not the best transitive-closure algorithm to use for sparse graphs. • For sparse graphs, you may be better off just doing DFS from each node v in turn, keeping track of which nodes are reached from v. Floyd's Algorithm • Floyd's algorithm solves the all-pairs shortest-path problem for weighted graphs with positive weights. • It works for directed as well as undirected graphs. • We assume we are given a weight matrix W that holds all the edges' weights • If there is no edge from node i to node j, we set W[i,j] = ∞. • We will construct the distance matrix D, step by step. a b c d 3 1 2 5 3 Floyd's Algorithm • Floyd's algorithm solves the all-pairs shortest-path problem for weighted graphs with positive weights. • It works for directed as well as undirected graphs. • We assume we are given a weight matrix W that holds all the edges' weights • If there is no edge from node i to node j, we set W[i,j] = ∞. • We will construct the distance matrix D, step by step. a b c d 3 1 2 5 3 Floyd's Algorithm • As we did in the Warshall's algorithm, assume nodes are numbered 1 to n. Floyd's Algorithm • As we did in the Warshall's algorithm, assume nodes are numbered 1 to n. • What is the shortest path from node i to node j using nodes [1 … k] as “stepping stones”? • Such path will exist if and only if we can: • step from i to j using only nodes [1 … k-1], or • step from i to k using only nodes [1 … k-1], and then step from k to j using only nodes [1 … k-1]. Floyd's Algorithm • If G’s weight matrix is W then we can express the recurrence relation as: • A simpler version updating D: Floyd's Algorithm • Let’s examine this algorithm. Let our graph be. • Then, the weight matrix is: 1 2 5 3 47 6 9 7 4 5 6 2 6 7 6 4 7 Floyd's Algorithm • For k=1 there are no changes. Floyd's Algorithm • For k=2, D[1,2] = 9 and D[2,3]=5; and D[4,2] = 4 and D[2,3]=5. • Hence, we can make D[1,3]=14 and D[4,3]=9 • Note that the graph is undirected, which makes the matrix symmetric. Floyd's Algorithm • For k=2, D[1,2] = 9 and D[2,3]=5; and D[4,2] = 4 and D[2,3]=5. • Hence, we can make D[1,3]=14 and D[4,3]=9 • Note that the graph is undirected, which makes the matrix symmetric. Floyd's Algorithm • For k=3, we can reach all other nodes in the graph. • However, these may not be the shortest paths. Floyd's Algorithm • For k=3, we can reach all other nodes in the graph. • However, these may not be the shortest paths. Floyd's Algorithm • Let’s look at the final steps: k=4 Floyd's Algorithm • Let’s look at the final steps: k=4 k=5 Floyd's Algorithm • Let’s look at the final steps: • For k=7, it is unchanged. So we have found the best paths. k=4 k=5 k=6 A Sub-Structure Property • For a DP approach to be applicable, the problem must have a “sub- structure” that allows for a compositional solution. • Shortest-path problems have this property. For example, if {x1, x2,…, xi, …, xn} is a shortest path from x1 to xn then {x1, x2,…, xi} is a shortest path from x1 to xn. • Longest-path problems don't have that property. • In our sample graph, {1,2,5,6,7,4,3} is a longest path from 1 to 3, but {1,2} is not a longest path from 1 to 2 (since {1,5,6,7,4,3,2} is longer). 1 2 5 3 47 6 9 7 4 5 6 2 6 7 6 4 7 Next lecture • Greedy algorithms