CS代考 COMP90038 Algorithms and Complexity

COMP90038 Algorithms and Complexity
Dynamic Programming: Warshall and Ohrimenko
(Slides from Harald Søndergaard)
Lecture 19
Semester 2, 2021
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 1 / 29

Announcements
Assignment 2 is out on LMS.
Olya’s consultation sessions (Zoom links via LMS):
Tuesday October 5, 2:30 – 3:30 pm Tuesday October 12, 2:30 – 3:30 pm
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 2 / 29

Dynamic Programming and Graphs
In the last lecture we looked at dynamic programming.
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.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 3 / 29

Left blank
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 4 / 29

Warshall’s Algorithm
Warshall’s algorithm computes the transitive closure of a binary relation (or a directed graph), presented as a matrix.
An edge (a,z) is in the transitive closure of graph G iff there is a pathinG fromatoz.
Warshall’s algorithm was not originally thought of as an instance of dynamic programming, but it fits the bill.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 5 / 29

Transitive Closure over a State Space
Transitive closure is important in all sorts of applications where we want to see if some “goal state” is reachable from some “initial state”.
Applications: compilers, maps, social networks.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 6 / 29

Reasoning about Transitive Closure
Assume the nodes of graph G are numbered from 1 to n.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 7 / 29

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 i to node j 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 stepfromi toj usingonlynodes ≤k−1,or
step from i to k using only nodes ≤ k −1, and then stepfromk toj usingonlynodes ≤k−1.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 7 / 29

Warshall’s Algorithm
If G’s adjacency matrix is A then we can express the recurrence
relation as
R0 = A[i,j] ij
Rk = Rk−1 or (Rk−1 and Rk−1) ij ij ik kj
This gives us a dynamic-programming algorithm:
function Warshall(A[·, ·], n) R0 ←A
for k ← 1 to n do for i ← 1 to n do
for j ← 1 to n do
Rk [i, j] ← Rk−1[i, j] or (Rk−1[i, k] and Rk−1[k, j])
return Rn
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 8 / 29

Warshall’s Algorithm
If we allow input A to be used for the output, we can simplify things.
Namely, if Rk−1[i,k] (that is, A[i,k]) is 0 then the assignment is doing nothing. And if it is 1, and if A[k,j] is also 1, then A[i,j] gets set to 1. So:
for k ← 1 to n do for i ← 1 to n do
for j ← 1 to n do if A[i,k] then
if A[k,j] then A[i,j] ← 1
But now we notice that A[i,k] does not depend on j, so testing it can be moved outside the innermost loop.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 9 / 29

Warshall’s Algorithm
This leads to a better version of Warshall’s algorithm:
for k ← 1 to n do for i ← 1 to n do if A[i,k] then
for j ← 1 to n do if A[k,j] then A[i,j] ← 1
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.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 10 / 29

Example of Running Warshall’s Algorithm
1234567
1 2 3 4 5 6 7
11 1
11 1
11 11
1
for k ← 1 to n do for i ← 1 to n do if A[i,k] then
for j ← 1 to n do if A[k,j] then A[i,j] ← 1
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 11 / 29

Example of Running Warshall’s Algorithm
1234567
1 2 3 4 5 6 7
111 1
11 1
111 11
1
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 12 / 29

Example of Running Warshall’s Algorithm
1234567
1 2 3 4 5 6 7
11 111 111 11 111 11 11 11
1
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 13 / 29

Example of Running Warshall’s Algorithm
1234567
1 2 3 4 5 6 7
11 111 111 11 111 11 11 11 11 11 11
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 14 / 29

Example of Running Warshall’s Algorithm
1234567
1 2 3 4 5 6 7
111111 11 11 11 11 11 11
111 11 11 11 11 11
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 16 / 29

Analysis of Warshall’s Algorithm
The analysis is straightforward.
Warshall’s algorithm, as it is usually presented, is Θ(n3), 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 v in turn, keeping track of which nodes are reached from v.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 18 / 29

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 W that holds all the edges’ weights (for technical reasons, if there is no edge from node i to node j, we let W[i,j] = ∞).
We will construct the distance matrix D, step by step.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 19 / 29

Transitive Closure and All-Pairs Shortest-Paths
bd
a
fgh
ce
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 20 / 29

Floyd’s Algorithm: All-Pairs Shortest-Paths
3b6d4 a42fg9h
1c e1 3
We want to construct a matrix D that gives us the shortest path for each pair (u,v) of nodes.
It should tell us, for example, that the shortest path from a to f has length 5, the shortest path from d to f has length 3, and the shortest pathfromf tohis∞.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 21 / 29

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 n.
This time ask the question: What is the shortest path from node i to node j using only nodes ≤ k as “stepping stones”?
We either use node k as a stepping stone, or we avoid it. So again, we can
stepfromi toj usingonlynodes ≤k−1,or
step from i to k using only nodes ≤ k −1, and then step
from k to j using only nodes ≤ k − 1.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 22 / 29

Floyd’s Algorithm
If G’s weight matrix is W then we can express the recurrence relation for minimal distances as follows:
D0 = W[i,j] ij
k k−1 k−1 k−1 Dij = min(Dij ,Dik +Dkj )
And then the algorithm follows easily:
function Floyd(W [·, ·], n) D←W
for k ← 1 to n do for i ← 1 to n do
for j ← 1 to n do
D[i, j] ← min(D[i, j], D[i, k] + D[k, j])
return D
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 23 / 29

Example of Running Floyd’s Algorithm
12
345
12345
1 2 3 4 5
0111∞ 10∞11 1∞01∞ 11101 ∞1∞10
The initial distance matrix
(for the unweighted graph above)
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 24 / 29

Example of Running Floyd’s Algorithm
12
345
12345
1 2 3 4 5
0111∞ 10211 1201∞ 11101 ∞1∞10
Distance matrix after first round (k = 1)
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 25 / 29

Example of Running Floyd’s Algorithm
12
345 Distance matrix after second
round (k = 2).
In this example, no change happens in the following round (k = 3).
12345
1 2 3 4 5
01112 10211 12013 11101 21310
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 26 / 29

Example of Running Floyd’s Algorithm
12
345 Distance matrix after fourth round
(k = 4).
In this example, no further change happens for k = 5, so this is the final result.
12345
1 2 3 4 5
01112 10211 12012 11101 21210
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 27 / 29

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 x1 –x2 –···–xi –···–xn is a shortest path from x1 to xn then x1 – x2 –···– xi is a shortest pathfromx1 toxi.
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).
12
345
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 28 / 29

Summary and Next Lecture
Today we applied dynamic programming to two graph problems:
Computing the transitive closure of a directed graph (Warshall’s algorithm)
Finding shortest distances in weighted directed graphs (Floyd’s algorithm)
Next lecture: Is Greed Good? Find out next when we discuss greedy algorithms.
Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 29 / 29

Related Posts