# CS代考 COMP90038 Algorithms and Complexity – cscodehelp代写

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”?

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

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 15 / 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

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 17 / 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.

Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 18 / 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”?

Algorithms and Complexity (Sem 2, 2021) Warshall and Floyd’s algorithms © University of Melbourne 22 / 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