COMP90038 – Algorithms and Complexity Lecture 19
COMP90038 Algorithms and Complexity
Lecture 19: Warshall and Floyd
(with thanks to Harald Søndergaard & Michael Kirley)
Casey Myers Casey.Myers@unimelb.edu.au David Caro Building (Physics) 274
COMP90038 – Algorithms and Complexity
Lecture 19
Review from Lecture 18: Dynamic Programming
•
•
• •
Dynamic programming is an algorithm design technique that is sometimes applicable when we want to solve a recurrence relation and the recursion involves overlapping instances.
In Lecture 16 we achieved a spectacular performance improvement in the calculation of Fibonacci numbers by switching from a naïve top-down algorithm to one that solved, and tabulated, smaller sub-problems.
The bottom-up approach used the tabulated results, rather than solving overlapping sub-problems repeatedly.
That was a particularly simple example of dynamic programming.
COMP90038 – Algorithms and Complexity
Lecture 19
Review from Lecture 18: Dynamic Programming
• Since all values S(1) to S(n) need to be found anyway, we may as well proceed from the bottom up, storing intermediate results in an array S as we go.
• Given an array C that holds the coin values, the recurrence relation tells us what to do:
COMP90038 – Algorithms and Complexity
Lecture 19
Review from Lecture 18: Dynamic Programming
• We can say the same thing formally, as a recurrence relation: 𝑆𝑖 =𝑚𝑎𝑥𝑆𝑖−1,𝑆𝑖−2 +𝑣!
• This holds for 𝑖 > 1.
• We need two base cases: S(0) = 0 and S(1) = 𝑣”.
COMP90038 – Algorithms and Complexity
Lecture 19
Review from Lecture 18: Dynamic Programming
• In Lecture 5 we looked at the knapsack problem.
• Given n items with
– weights:𝑤”,𝑤#,⋯,𝑤$ – values:𝑣”,𝑣#,⋯,𝑣$
– knapsack of weight capacity W.
• Find the most valuable selection of items that will fit in the knapsack.
• We assume that all entities involved are positive integers.
COMP90038 – Algorithms and Complexity
Lecture 19
Review from Lecture 18: Dynamic Programming
• First fill the leftmost column and top row, then proceed row by row:
• The algorithm has time (and space) complexity Θ 𝑛𝑊 .
COMP90038 – Algorithms and Complexity Lecture 19
Directed Graphs
• A directed graph:
EF
HG
• And the adjacency matrix for this graph:
E F G H
EFGH
0101 1010 1000 0000
COMP90038 – Algorithms and Complexity Lecture 19
Directed Graphs
• A directed graph:
EF
HG
• And the adjacency matrix for this graph:
E F G H
EFGH
0111 1010 1000 0000
COMP90038 – Algorithms and Complexity
Lecture 19
Dynamic Programming and Graphs
• In the last lecture we looked at dynamic programming.
• We now apply dynamic programming to two graph problems: For dynamic
programming to be useful, the optimality principle must hold: – Computing the transitive closure of a directed graph; and – Finding shortest distances in weighted directed graphs.
COMP90038 – Algorithms and Complexity Lecture 19
Warshall’s Algorithm
• Warshall’s algorithm computes the transitive closure of a binary relation (or a directed graph), presented as a matrix.
• An edge 𝑎, 𝑧 is in the transitive closure of graph G iff there is a path in G from 𝑎 to z.
• Warshall’s algorithm was not originally thought of as an instance of dynamic programming but it fits the bill.
COMP90038 – Algorithms and Complexity
Lecture 19
Transitive Closure over a State Space
• Transitive closure is important in all sorts of applications where we want to see of some “goal start” is reachable from some “initial state”.
• For example is there a sequence of steps that will allow the containers of a ship to be reorganised in a certain way?
COMP90038 – Algorithms and Complexity
Lecture 19
Reasoning about Transitive Closure
• Assume the nodes of graph G are numbered from 1 to n.
• Ask the question: Is there a path from node 𝑖 to node 𝑗 using only nodes that are no larger than some k as “stepping stones”?
COMP90038 – Algorithms and Complexity
Lecture 19
Reasoning about Transitive Closure
• Assume the nodes of graph G are numbered from 1 to n.
• Ask the question: Is there a path from node 𝑖 to node 𝑗 using only nodes that are no
larger than some k as “stepping stones”?
• Such a path either uses node k as a stepping stone, or it doesn’t.
• So an answer is: There is such a path if and only if we can step from 𝑖 to 𝑗 using only nodes ≤ 𝑘 − 1, or
step from 𝑖 to k using only nodes ≤ 𝑘 − 1, and then step from k to j using only nodes ≤ 𝑘 − 1.
COMP90038 – Algorithms and Complexity Lecture 19
Warshall’s Algorithm
• If 𝐺’s adjacency matrix is 𝐴 then we can express the recurrence relation as 𝑅& =𝐴𝑖,𝑗
𝑅’ = 𝑅'(” or 𝑅'(” and 𝑅'(” !% !% !’ ‘%
!%
COMP90038 – Algorithms and Complexity Lecture 19
Warshall’s Algorithm
• If 𝐺’s adjacency matrix is 𝐴 then we can express the recurrence relation as 𝑅& =𝐴𝑖,𝑗
𝑅’ = 𝑅'(” or 𝑅'(” and 𝑅'(” !% !% !’ ‘%
Use the existing path created in the previous step
!%
COMP90038 – Algorithms and Complexity Lecture 19
Warshall’s Algorithm
• If 𝐺’s adjacency matrix is 𝐴 then we can express the recurrence relation as 𝑅& =𝐴𝑖,𝑗
𝑅’ = 𝑅'(” or 𝑅'(” and 𝑅'(” !% !% !’ ‘%
Or create a new path using 𝑘 as an intermediate step
!%
COMP90038 – Algorithms and Complexity Lecture 19
Warshall’s Algorithm
• If 𝐺’s adjacency matrix is 𝐴 then we can express the recurrence relation as 𝑅& =𝐴𝑖,𝑗
𝑅’ = 𝑅'(” or 𝑅'(” and 𝑅'(” !% !% !’ ‘%
• This gives us a dynamic programming algorithm:
!%
COMP90038 – Algorithms and Complexity Lecture 19
Warshall’s Algorithm
• If we allow input A to be used for the output, we can simplify things.
• Namely, if 𝑅'(” 𝑖, 𝑘 (that is, 𝐴 𝑖, 𝑘 ) is 0, then the assignment is doing nothing.
And if it is 1, and if 𝐴 𝑘, 𝑗 is also 1, then 𝐴 𝑖, 𝑗 gets set to 1. So:
• But now we notice that 𝐴 𝑖, 𝑘 does not depend on j, so testing it can be moved outside the innermost loop.
COMP90038 – Algorithms and Complexity Lecture 19
Warshall’s Algorithm
• This leads to a better version of Warshall’s algorithm:
• If each row in the matrix is represented as a bit-string, the innermost for loop (and 𝑗) can be gotten rid of–instead of iterating, just apply the “bitwise or” of row k to row i.
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
1
1
0
2 3 4
k = 1: nothing, not change 5 6 7
234567
010000 000011 010000 100010 001001 001000
0 0 0 0 0 0
100100
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
1 34567 1 0 00100
0 00011 0 10000 0 00010 0 01001 0 01000
3
4 k = 2: 𝑖 values A 𝑖, 𝑘 : 1, 5 5
j values A 𝑘, 𝑗 : 3 6
A 1,3 = 1 A 5,3 = 1
7
2
0
2
1
0
0 0 1 0 0
10000
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
12 4567 1 01 0100
00 0000
00 0000 01 0010 00 1001 00 1000
2 4
k= 3: 𝑖 values A 𝑖, 𝑘 : 1, 2, 4, 5 5 j values A 𝑘, 𝑗 : 6,7 6
3
00
3
1
1
0
1
1
0 0
0011
A1,6 =1,A1,7 =1 A2,6 =1,A2,7 =1 A4,6 =1,A4,7 =1 A5,6 =1,A5,7 =1
7
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
123 567
1 011 111
001 011 000 011
011 011 000 001 000 000
2 3
k = 4: 𝑖 values A 𝑖, 𝑘 : 6, 7 5 j values A 𝑘, 𝑗 : 3,6,7 6
A 6,3 = 1, A 6,6 = 1, A 6,7 = 1 7 A 7,3 =1,A 7,6 =1,A 7,7 =1
4
001
4
0 0 0
0
0 1 1
011
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
k = 5: 𝑖 values A 𝑖, 𝑘 : 1
j values A 𝑘, 𝑗 : 2,3,6,7
A1,2 =1,A1,3 =1, A1,6 =1,A1,7 =1
2 3 4
6 7
1234 67
1 0110 11
0010 11 0000 11 0010 11
0011 11 0011 11
5
0110
5
1 0 0 0
0
0 0
11
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
12345 7
1 01101 1
00100 1 00000 1 00100 1 01100 1
00110 1
2 3 4
k=6:𝑖valuesA𝑖,𝑘:1,2,3,4,5,6,7 5 j values A 𝑘, 𝑗 : 3,4,6,7
7
6
00110
6
1 1 1 1 1
1
1
1
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
123456
1 011111
001101 001101 001101 011101 001101
2 3 4
k=7:𝑖valuesA𝑖,𝑘:1,2,3,4,5,6,7 5 j values A 𝑘, 𝑗 : 3,4,6,7 6
7
001101
7
1 1 1 1 1 1
1
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
1234567
1 0111111
0011011 0011011 0011011 0111011 0011011 0011011
2 3 4 5 6 7
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
a b c d
abcd
0100 0001 0000 1010
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm: Extended
k = 1: 𝑖 values A 𝑖, 𝑘 : 4 j values A 𝑘, 𝑗 : 2
A 4,2 = 1
abcd abcd
0
aa
b 001 b0001 c 000 c0000 d 010 d1110
0100
0 0 1
100
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm: Extended
k = 2: 𝑖 values A 𝑖, 𝑘 : 1, 4 j values A 𝑘, 𝑗 : 4
A1,4 =1,A4,4 =1
abcd abcd a000 a0101
0
1
0001 d110 d1111
0
bb c000 c0000
0 1
01
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm: Extended
00
0 0
0
k=3:𝑖valuesA𝑖,𝑘: 4 j values A 𝑘, 𝑗 : −
abcd abcd a011 a0101
b001 b0001
cc d111 d1111
1
0
0000
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm: Extended
k = 4: 𝑖 values A 𝑖, 𝑘 : 1,2, 4 j values A 𝑘, 𝑗 : 1,2,3,4
A 1,1 =1,A 1,2 =1,A 1,3 =1,A 1,4 =1 A 2,1 =1,A 2,2 =1,A 2,3 =1,A 2,4 =1 A 4,1 =1,A 4,2 =1,A 4,3 =1,A 4,4 =1
abcd abcd
a 010
b 000
a 1111
b 1111
c 0000
1111
c 000 dd
111
1 1 0
1
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Warshall’s Algorithm
abcd abcd
a 0100 a 1111 b0001⇒b1111 c 0000 c 0000 d 1010 d 1111
Correction from lecture slide
COMP90038 – Algorithms and Complexity
Lecture 19
Analysis of Warshall’s Algorithm
• The analysis is straightforward.
• Warshall’s algorithm, as it is usually presented, is Θ(𝑛)), and 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 𝑣 in turn, keeping track of which nodes are reached from 𝑣.
COMP90038 – Algorithms and Complexity
Lecture 19
Floyd’s Algorithm: All-Pairs Shortest-Paths
• 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.
• (It also works, in some circumstances, when there are non-positive weights in the
graph, but not always. )
• We assume we are given a weight matrix 𝑊 that holds all the edges’ weights (for
technical reasons, if there is no edge from node 𝑖 to node j, we let 𝑊 𝑖, 𝑗 = ∞).
• We will construct the distance matrix 𝐷, step by step.
COMP90038 – Algorithms and Complexity Lecture 19
Floyd’s Algorithm
• We can use the same problem decomposition as we used to derive Warshall’s algorithm. Again assume nodes are numbered 1 to 𝑛.
• This time ask the question: What is the shortest path from node 𝑖 to node 𝑗 using only nodes ≤ 𝑘 as “stepping stones”?
1234
0 5 ∞ 10 ∞03∞ ∞∞01 ∞∞∞0
1 2 3 4
COMP90038 – Algorithms and Complexity Lecture 19
Floyd’s Algorithm
• We can use the same problem decomposition as we used to derive Warshall’s algorithm. Again assume nodes are numbered 1 to 𝑛.
• This time ask the question: What is the shortest path from node 𝑖 to node 𝑗 using only nodes ≤ 𝑘 as “stepping stones”?
1234
05∞9 ∞03∞ ∞∞01 ∞∞∞0
1 2 3 4
COMP90038 – Algorithms and Complexity Lecture 19
Floyd’s Algorithm
• We can use the same problem decomposition as we used to derive Warshall’s algorithm. Again assume nodes are numbered 1 to 𝑛.
• This time ask the question: What is the shortest path from node 𝑖 to node 𝑗 using only nodes ≤ 𝑘 as “stepping stones”?
• We either use node 𝑘 as a stepping stone, or we avoid it. So again, we can step from 𝑖 to 𝑗 using only nodes ≤ 𝑘 − 1, or
step from 𝑖 to k using only nodes ≤ 𝑘 − 1, and then step from k to j using only nodes ≤ 𝑘 − 1.
COMP90038 – Algorithms and Complexity Lecture 19
Floyd’s Algorithm
• If 𝐺’s weight matrix is 𝑊 then we can express the recurrence relation for minimal distances as follows:
𝐷& =𝑊𝑖,𝑗 !%
𝐷’ = min 𝐷'(“, 𝐷'(” + 𝐷'(” !% !% !’ ‘%
• And then the algorithm follows easily:
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
• The initial distance matrix (for the unweighted graph above).
12345 10111∞
210∞11
k = 1: 𝑖 values D 𝑖, 𝑘 : 2,3,4 3
1∞01∞
11101 ∞1∞10
j values D 𝑘, 𝑗 : 2,3,4
D2,3 =1+1=2 D3,2 =1+1=2
4 5
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
• Distance matrix after first round (𝑘 = 1).
12345
10111∞
10211 1201∞ 11101
∞1∞10
k = 2: 𝑖 values D 𝑖, 𝑘 : 1,3,4,5 3
2
j values D 𝑘, 𝑗 : 1,3,4,5 D1,5 =1+1=2 D3,5 =2+1=3 D5,1 =1+1=2
4 5
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
• Distance matrix after second round (𝑘 = 2).
• In this example, no change happens in the following round (𝑘 = 3).
12345
101112 210211 312013
411101
21310
5
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
• Distance matrix after second round (𝑘 = 2).
• In this example, no change happens in the following round (𝑘 = 3).
k = 4: 𝑖 values D 𝑖, 𝑘 : 1,2,3,5 j values D 𝑘, 𝑗 : 1,2,3,5
12345
101112 210211 312013 411101 521310
D5,3 =1+1=2
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
• Distance matrix after fourth round (𝑘 = 4).
12345
101112
10211 12012 11101 21210
• In this example, no further change happens for 𝑘 = 5, so this is the final result.
2 3 4 5
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
a b c d
abcd
0∞3∞
20∞∞ ∞701 6∞∞0
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
k = 1: 𝑖 values D 𝑖, 𝑘 : 2,4 j values D 𝑘, 𝑗 : 3
D2,3 =2+3=5 D4,3 =3+6=9
abcd abcd
0
aa
b 0∞∞ b205∞ c 701 c∞701 d ∞∞0 d6∞90
0∞3∞
2 ∞ 6
∞3∞
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
k = 2: 𝑖 values D 𝑖, 𝑘 : 3
j values D 𝑘, 𝑗 : 1,3
D3,1 =7+2=9
abcd abcd a0∞3∞ a0∞3∞
2
0
5∞
205∞ d6∞90 d6∞90
bb c∞701 c9701
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
k = 3: 𝑖 values D 𝑖, 𝑘 : 1,2,4 j values D 𝑘, 𝑗 : 1,2,4
D 1,2 =3+7=10,D 1,4 =3+1=4 D 2,1 =5+9=14,D 2,4 =5+1=6
D 4,1 =9+9=18,D 4,2 =9+7=16
abcd abcd a 0 ∞ ∞ a 0 10 3 4
b20∞ b2056
97
3 5
0
cc
d6∞ 0 d61690
9
9701
1
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
k = 4: 𝑖 values D 𝑖, 𝑘 : 1,2,3 j values D 𝑘, 𝑗 : 1,2,3
D 1,2 =4+16=20,D 1,3 =4+9=15 D 2,1 =6+6=12,D 2,3 =6+9=15 D 3,1 =1+6=7,D 3,2 =1+16=17
abcd abcd
a 0 10 3 a 0 10 3 4
b205 b2056
c970 c7701
6 16 9
4 6 1
0
dd
6 16 9 0
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
abcd abcd
a 0 ∞ 3 ∞ a 0 10 3 4 b20∞∞ ⇒ b2056 c∞701 c7701 d 6 ∞ ∞ 0 d 6 16 9 0
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
1 2 3 4 5 6 7
1234567
09∞∞7∞∞
905∞4∞∞ ∞506∞26 ∞∞60∞76
74∞∞04∞ ∞∞27407 ∞∞66∞70
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
0
1 2 3 4 5 6 7
1234567
05∞4∞∞
506∞26 ∞60∞76
4∞∞04∞ ∞27407 ∞66∞70
k = 1: 𝑖 values D 𝑖, 𝑘 : 2,5 j values D 𝑘, 𝑗 : 2,5
D 2,5 =9+7=16,D 5,2 =7+9=16
1 2 3 4 5 6 7
1234567
09∞∞7∞∞
905∞4∞∞ ∞506∞26 ∞∞60∞76
74∞∞04∞ ∞∞27407 ∞∞66∞70
9 ∞ ∞ 7 ∞ ∞
9∞∞7∞∞
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
k = 2: 𝑖 values D 𝑖, 𝑘 : 1,3,5 j values D 𝑘, 𝑗 : 1,3,5
D 1,3 =9+5=14,D 1,5 =9+4=13 D 3,1 =5+9=14,D 3,5 =5+4=9 D 5,1 =4+9=13,D 5,3 =4+5=9
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1234567
0 ∞∞7∞∞
∞ 06∞26 ∞ 60∞76
7 ∞∞04∞ ∞ 27407 ∞ 66∞70
1234567
0 9 14 ∞ 7 ∞ ∞
905∞4∞∞ 14 5 0 6 9 2 6 ∞∞60∞76
749∞04∞ ∞∞27407 ∞∞66∞70
9
9
0
5 ∞ 4 ∞ ∞
5∞4∞∞
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
1234567
109∞7∞∞
90 ∞4∞∞
∞∞ 0∞76 74 ∞04∞
∞∞ 7407
∞∞ 6∞70
1234567
0 9 14 20 7 16 20
9 0 5 11 4 7 11 14 5 0 6 9 2 6 20 11 6 0 15 7 6
7 4 9 15 0 4 15 16 7 2 7 4 0 7 20 11 6 6 15 7 0
2 3 4 5 6 7
14 5
14 5
0
k = 3: 𝑖 values D 𝑖, 𝑘 : 1,2,4,5,6,7 j values D 𝑘, 𝑗 : 1,2,4,5,6,7
1
6 9 2 6
6926
D1,2 =19,D1,4 =20,D1,5 =23,D1,6 =16,D1,7 =20 2 D2,1 =19,D2,4 =11,D2,5 =14,D2,6 =7,D2,7 =11
D4,1 =20,D4,2 =11,D4,5 =15,D4,6 =8,D4,7 =12 3 D5,1 =23,D5,2 =14,D5,4 =15,D5,6 =11,D5,7 =15 D6,1 =16,D6,2 =7,D6,4 =8,D6,5 =11,D6,7 =8
4
D7,1 =20,D7,2 =11,D7,4 =12,D7,5 =15,D7,6 =8
5
6 7
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
20 11 6
20 11 6
0
k = 4: 𝑖 values D 𝑖, 𝑘 : 1,2,3,5,6,7 j values D 𝑘, 𝑗 : 1,2,3,5,6,7
1 2 3 4 5 6 7
1
1234567
0914 71620
905 4711 1450 926
749 0415 1672 407 20116 15 7 0
1234567
0 9 14 20 7 16 20
9 0 5 11 4 7 11 14 5 0 6 9 2 6 20 11 6 0 15 7 6
7 4 9 15 0 4 15 16 7 2 7 4 0 7 20 11 6 6 15 7 0
15 7 6
15 7 6
D1,2 =31,D1,3 =26,D1,5 =35,D1,6 =27,D1,7 =26 2 D2,1 =31,D2,3 =17,D2,5 =26,D2,6 =18,D2,7 =17 D3,1 =26,D3,2 =17,D3,5 =21,D3,6 =13,D3,7 =12 3 D5,1 =35,D5,2 =26,D5,3 =21,D5,6 =22,D5,7 =21 D6,1 =27,D6,2 =18,D6,3 =13,D6,5 =22,D6,7 =13 D7,1 =26,D7,2 =17,D7,3 =12,D7,5 =21,D7,6 =13
4 5 6 7
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
7 4 9 15
7 4 9 15
0
k = 5: 𝑖 values D 𝑖, 𝑘 : 1,2,3,4,6,7 j values D 𝑘, 𝑗 : 1,2,3,4,6,7
1 2 3 4 5 6 7
1
1234567
091420 1620
9 0 5 11 711 14506 26 201160 76
4 15 16727 07 201166 70
1234567
0 9 14 20 7 11 20
9 0 5 11 4 7 11 14 5 0 6 9 2 6 20 11 6 0 15 7 6
7 4 9 15 0 4 15 11 7 2 7 4 0 7 20 11 6 6 15 7 0
4 15
D1,2 =11,D1,3 =16,D1,4 =22,D1,6 =11,D1,7 =22 2 D2,1 =11,D2,3 =13,D2,4 =19,D2,6 =8,D2,7 =19
D3,1 =16,D3,2 =13,D3,4 =24,D3,6 =13,D3,7 =24 3 D4,1 =22,D4,2 =19,D4,3 =24,D4,6 =19,D4,7 =30 D6,1 =11,D6,2 =8,D6,3 =13,D6,4 =19,D6,7 =19
4
D7,1 =22,D7,2 =19,D7,3 =24,D7,5 =30,D7,6 =19
5
6 7
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
11 7 2 7 4
11 7 2 7 4
0
k = 6: 𝑖 values D 𝑖, 𝑘 : 1,2,3,4,5,7 j values D 𝑘, 𝑗 : 1,2,3,4,5,7
1 2 3 4 5 6 7
1
1234567
0914207 20
9 0 5 11 4 11 14 5 0 6 9 6 20 11 6 0 15 6
7 4 9 15 0 15
20 11 6 6 15 0
1234567
0 9 13 18 7 11 18
9 0 5 11 4 7 11 13 5 0 6 6 2 6 18 11 6 0 11 7 6
7 4 6 11 0 4 11 11 7 2 7 4 0 7 18 11 6 6 11 7 0
7
7
D1,2 =18,D1,3 =13,D1,4 =18,D1,5 =15,D1,7 =18 2 D2,1 =18,D2,3 =9,D2,4 =14,D2,5 =11,D2,7 =14
D3,1 =13,D3,2 =9,D3,4 =9,D3,5 =6,D3,7 =9 3 D4,1 =18,D4,2 =14,D4,3 =9,D4,5 =11,D4,7 =14
D5,1 =15,D5,2 =11,D5,3 =6,D5,4 =11,D5,7 =11 D7,1 =18,D7,2 =14,D7,3 =9,D7,4 =14,D7,5 =11
4 5 6 7
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm: Extended
18 11 6 6 11 7
18 11 6 6 11 7
0
k = 7: 𝑖 values D 𝑖, 𝑘 : 1,2,3,4,5,6 j values D 𝑘, 𝑗 : 1,2,3,4,5,6
1 2 3 4 5 6 7
1
1234567
0 9 13 18 7 11
9 0 5 11 4 7 13 5 0 6 6 2 18 11 6 0 11 7
7 4 6 11 0 4 11 7 2 7 4 0
1234567
0 9 13 18 7 11 18
9 0 5 11 4 7 11 13 5 0 6 6 2 6 18 11 6 0 11 7 6
7 4 6 11 0 4 11 11 7 2 7 4 0 7 18 11 6 6 11 7 0
D1,2 =29,D1,3 =24,D1,4 =24,D1,5 =29,D1,6 =25 2 D2,1 =29,D2,3 =17,D2,4 =17,D2,5 =22,D2,6 =18 D3,1 =24,D3,2 =17,D3,4 =12,D3,5 =17,D3,6 =13 3 D4,1 =24,D4,2 =17,D4,3 =12,D4,5 =17,D4,6 =13 D5,1 =29,D5,2 =22,D5,3 =17,D5,4 =17,D5,6 =18 D6,1 =25,D6,2 =18,D6,3 =13,D6,4 =13,D6,5 =18
4 5 6 7
COMP90038 – Algorithms and Complexity
Lecture 19
Example of Running Floyd’s Algorithm
1 2 3 4 5 6 7
1234567
09∞∞7∞∞
905∞4∞∞ ∞506∞26 ∞∞60∞76
74∞∞04∞ ∞∞27407 ∞∞66∞70
1234567
0 9 13 18 7 11 18
9 0 5 11 4 7 11 13 5 0 6 6 2 6 18 11 6 0 11 7 6
7 4 6 11 0 4 11 11 7 2 7 4 0 7 18 11 6 6 11 7 0
1 2 3 4 5 6 7
COMP90038 – Algorithms and Complexity
Lecture 19
A Sub-Structure Property
• For a dynamic programming approach to be applicable, the problem must have a certain “sub-structure” property that allows for a compositional solution.
• Shortest-path problems have the property: if 𝑥” − 𝑥# − ⋯ − 𝑥! − ⋯ − 𝑥$ is a shortest path from 𝑥” to 𝑥$ then 𝑥” − 𝑥# − ⋯ − 𝑥! is a shortest path from 𝑥” to 𝑥! .
• Longest-path problems don’t have that property. In our sample graph 1−3−4−2−5 is a longest path from 1 to 5, but 1−3−4−2 is not a longest path from 1 to 2 (since 1−3−4−5−2 is longer).
COMP90038 – Algorithms and Complexity Lecture 19
Coming Up Next
• Greedy techniques
– Prim’s algorithm (Levitin Section 9.1)
– Dijkstra’s algorithm (Levitin Section 9.3).