CSC373H Lecture 5
October 6, 2021
Copyright By PowCoder代写 加微信 powcoder
All-Pairs Shortest Paths (APSP)
▶ Input: Directed graph G = (V , E ) with integer edge weights w(e). These weights can be negative, but assume no negative-weight cycle
▶ Output: for each u, v ∈ V , the length of a minimum-weight path from u to v
▶ We already know how to solve this problem by reducing it to n invocations of a single-source shortest paths algorithm (once per vertex)
▶ e.g. if all edge weights are nonnegative, then n invocations of Dijkstra is O(nm lg n). Not bad!
▶ But if there are negative-weight edges, then the alternative algorithms are slower than Dijkstra. Floyd can do better
APSP: Two Characterizations
▶ Two ways to characterize subproblems
▶ Restrict the number of edges on a path
▶ Restrict the allowed intermediate vertices on a path (Floyd)
▶ We’ll study Floyd here because it has the better time complexity of the two
Floyd: Step 1
▶ Arbitrarily number the vertices 1, 2, . . . , n ▶ Consider the shortest path P from u to v ▶ P is guaranteed not to have a cycle. Why?
▶ If it did, then we could remove the (non-negative weight) cycle from P to get an even shorter path
▶ Let k be the largest intermediate vertex on P
Floyd: Step 1…
Optimal substructure of shortest paths
▶ Claim: P consists of the shortest path p1 from u to k using vertices 1, 2, . . . , k − 1 followed by the shortest path p2 from k to v using vertices 1,2,…,k −1
▶ For contradiction, suppose that there is a path p1′ from u to k using vertices 1, 2, . . . , k − 1 that’s shorter than p1
▶ Then replace p1 with p1′ in the shortest path from u to v to get an even better path than P
▶ If this even better path has a cycle, then remove the cycle to make it a simple path again
▶ (Analogous proof for p2)
Floyd: Step 2
▶ We have our first example of a 3d dynamic programming array ▶ A[k, u, v] is the shortest path from u to v using intermediate
vertices in 1,2,…,k
▶ When k = 0, the paths have no intermediate vertices
Floyd: Step 3
w[u,v],
A[k,u,v] =
min {A[k−1,u,v],A[k−1,u,k]+A[k−1,k,v]}
if k = 0 and u = v
if k = 0 and (u,v) ∈ E if k = 0 and (u,v) ̸∈ E if k > 0
Floyd: Step 4
for u in [1,…,n]: # base cases
for v in [1,…,n]:
if u == v:
A[0,u,v] = 0
else if (u,v) in E:
A[0,u,v] = w(u,v)
A[0,u,v] = infinity
for k in [1,…,n]: # general
for u in [1,…,n]:
for v in [1,…,n]:
if A[k-1,u,k] + A[k-1,k,v] < A[k-1,u,v]:
A[k,u,v] = A[k-1,u,k] + A[k-1,k,v]
A[k,u,v] = A[k-1,u,v]
Floyd: Step 4...
▶ We have an n3 algorithm, and this is independent of number of edges in the graph
▶ The space used is n3 too
▶ Space optimization: we can improve the space to n2!
▶ Observation: on iteration k, imagine that we didn’t change any entry whose row or column is k
▶ Then we could drop the k subscript because we could use
A[k , ...] instead of A[k − 1, ...] for entries whose row or column is k
Floyd: Space Optimization
▶ Suppose u is k
▶ Then, to update A[k,k,v], we’d require
A[k − 1, k , k ] + A[k − 1, k , v ] < A[k − 1, k , v ]
▶ But this will never happen, because A[k − 1, k, k] = 0
▶ A similar argument holds when v is k
Floyd: Step 4...
for u in [1,...,n]: # base cases
for v in [1,...,n]:
if u == v:
A[u,v] = 0
else if (u,v) in E:
A[u,v] = w(u,v)
A[u,v] = infinity
for k in [1,...,n]: # general
for u in [1,...,n]:
for v in [1,...,n]:
if A[u,k] + A[k,v] < A[u,v]:
A[u,v] = A[u,k] + A[k,v]
Floyd: Step 5
▶ It helps to store additional information to make step 5 easier
▶ We will store the largest intermediate vertex on a path from each u to each v
▶ Entries of new array B ▶ −1: no path
▶ 0: largest intermediate vertex is 0 (i.e. no intermediate vertices at all)
▶ k > 0: k is largest intermediate vertex
Floyd: Step 5…
for u in [1,…,n]: # base cases
for v in [1,…,n]:
if u == v:
A[u,v] = 0; B[u,v] = -1
else if (u,v) in E:
A[u,v] = w(u,v); B[u,v] = 0
A[u,v] = infinity; B[u,v] = -1
for k in [1,…,n]: # general
for u in [1,…,n]:
for v in [1,…,n]:
if A[u,k] + A[k,v] < A[u,v]:
A[u,v] = A[u,k] + A[k,v]; B[u,v] = k
Floyd: Step 5...
Now we can recursively reconstruct the path.
def path(u, v): # assumes A and B are already generated
if B[u,v] > 0:
return path(u, B[u,v]) + path(B[u,v],v)
else if B[u,v] == 0:
return ([u,v]) # single edge
return [] # no path
Transitive Closure
▶ Input: Directed graph G = (V , E )
▶ Output: for each u, v ∈ V , indicate true if the vertices are connected and false otherwise
▶ We can solve this already in O(n3) time using Floyd. How? ▶ Give each edge a weight of 1 and run Floyd on the graph
▶ Then, u and v are connected iff A[u,v] < ∞
▶ However, we can actually do better than O(n3) for this problem!
Transitive Closure...
▶ Start with adjacency matrix
▶ Diagonal is 1 because each vertex is connected to itself ▶ Row u, column v is 1 iff there is an edge from u to v
1001 1100 1110 0001
Transitive Closure...
Let’s square this matrix (multiply it by itself):
1001 1101 1002 1100 x 1100 = 2101 1110 1110 3211 0001 0001 0001
▶ e.g.A2[2,4]=
A[2, 1]∗A[1, 4]+A[2, 2]∗A[2, 4]+A[2, 3]∗A[3, 4]+A[2, 4]∗A[4, 4]
▶ Itis≥1iffthereisapathofatmost2edgesfrom2to4
Transitive Closure...
▶ Our technique is to multiply by A a total of n − 1 times
▶ If matrix multiplication is O(n3), then we have an O(n4) algorithm
Transitive Closure: Trick 1
Use logical and instead of multiplication, and use logical or instead of addition.
▶ e.g.A2[2,4]=A[2,1]∧A[1,4]∨A[2,2]∧A[2,4]∨A[2,3]∧ A[3,4]∨A[2,4]∧A[4,4]
▶ Nowitis1iffthereisapathofatmost2edgesfrom2to4, and 0 otherwise
▶ Why do this?
▶ Bool values take up less space than integers
▶ Bool operations may be faster than integer operations
Transitive Closure: Trick 2
▶ Rather than computing A, A2, A3, . . ., we can use repeated squaring to reduce the number of matrix multiplications
▶ Compute A2, then (A2)2 = A4, then (A4)2 = A8 and so on
▶ This is only lg n matrix multiplications
▶ So, if matrix multiplication is O(n3), then we now have an O(n3 lg n) algorithm
Transitive Closure: Trick 3
▶ Matrix multiplication can be done in better than O(n3) time
▶ e.g. Strassen’s algorithm takes O(nlg2 7, which is O(n2.81) ▶ We now have an O(n2.81 lg n) algorithm
Longest Palindromic Subsequence (LPS)
▶ Input: string s
▶ Output: the longest palindromic subsequence in s
▶ A subsequence of a string s is s with one or more characters deleted
▶ A palindrome is a string that is equal to its reversal
▶ A palindromic subsequence is a subsequence that is a palindrome
LPS: Example
What is the LPS of this string?
AABCBABBCA
LPS: Let’s Try
Let’s try working through some steps toward a solution!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com