CSC373H Lecture 5
Dan Zingaro
October 17, 2016
All-Pairs Shortest Paths (APSP)
Input:DirectedgraphG=(V,E)withintegeredgeweights w(e), but 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)
For a dense graph where m = O(n2), this is O(n3 lg n)
We can do better for dense graphs . . .
APSP: Two Characterizations
Two ways to characterize subproblems
Restrict number of edges on path
Restrict the allowed intermediate vertices on a path (Floyd)
We’ll study Floyd because it has better time complexity
Floyd: Step 1
Arbitrarilynumberthevertices1,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 shorter path p1′ from u to k using vertices 1,2,…,k −1
Then replace p1 with p1′ in the shortest path from u to v to get an even better path
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 3d 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
0,
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)
else:
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]
else:
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
Supposeuisk
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 ]
Butthiswillneverhappen,becauseA[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)
else:
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
else:
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
else:
return [] # no path
Transitive Closure
Input:DirectedgraphG=(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 Rowu,columnvis1iffthereisanedgefromutov
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
RatherthancomputingA,A2,A3,...,wecanuserepeated squaring to reduce the number of matrix multiplications
Compute A2, then (A2)2 = A4, then (A4)2 = A8 and so on
Thisisonlylgnmatrixmultiplications
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