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
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 • theremainingcapacityw≤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
ab
cd
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
ab
cd
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:
2
513
74
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:
k=3 k=4 k=6
• At k=5 and k=7, there is no changes to the matrix.
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.
3 ab
3 c5d
12
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.
3 ab
3 c5d
12
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:
2
4 5 9
513 7
6
6
74 6
4
772 6
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:
k=4 k=5 k=6 • For k=7, it is unchanged. So we have found the best paths.
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).
2 4
513 7
6
6
74 6
5 9
4
772 6
Next lecture
• Greedy algorithms