Lecture 11: All-Pairs Shortest Paths

Lecture 11 All-Pairs Shortest Paths 6.046J Spring 2015 Lecture 11: All-Pairs Shortest Paths Introduction Different types of algorithms can be used to solve the all-pairs shortest paths problem: • Dynamic programming • Matrix multiplication • Floyd-Warshall algorithm • Johnson’s algorithm • Difference constraints Single-source shortest paths • given directed graph G = (V, E), vertex s ∈ V and edge weights w : E → R • find δ(s, v), equal to the shortest-path weight s− > v, ∀v ∈ V (or −∞ if negative weight cycle along the way, or ∞ if no path) Situtation unweighted (w = 1) non-negative edge weights general acyclic graph (DAG) Algorithm BFS Dijkstra Bellman-Ford Topological sort + one pass of B-F Time O(V + E) O(E + V lg V ) O(V E) O(V + E) All of the above results are the best known. We achieve a O(E + V lg V ) bound on Dijkstra’s algorithm using Fibonacci heaps. All-pairs shortest paths • given edge-weighted graph, G = (V, E, w) • find δ(u, v) for all u, v ∈ V 1 Lecture 11 6.046J Spring 2015 All-Pairs Shortest Paths A simple way of solving All-Pairs Shortest Paths (APSP) problems is by running a single-source shortest path algorithm from each of the V vertices in the graph. Situtation Algorithm unweighted (w = 1) |V |× BFS non-negative edge weights |V |× Dijkstra |V |× Bellman-Ford general general Johnson’s Time E = Θ(V 2 ) O(V 3 ) O(V E) O(V 3 ) O(V E + V 2 lg V ) O(V 2 E) O(V 4 ) O(V E + V 2 lg V ) O(V 3 ) These results (apart from the third) are also best known — don’t know how to beat |V |× Dijkstra Algorithms to solve APSP Note that for all the algorithms described below, we assume that w(u, v) = ∞ if (u, v) ∈ E. Dynamic Programming, attempt 1 (m) 1. Sub-problems: duv = weight of shortest path u → v using ≤ m edges 2. Guessing: What’s the last edge (x, v)? 3. Recurrence: (m−1) + w(x, v) for x ∈ V ) d(m) uv = min(dux d(0) uv = 0 if u = v ∞ otherwise 4. Topological ordering: for m = 0, 1, 2, . . . , n − 1: for u and v in V : 5. Original problem: If graph contains no negative-weight cycles (by Bellman-Ford analysis), then (n−1) (n) shortest path is simple ⇒ δ(u, v) = duv = duv = · · · Time complexity In this Dynamic Program, we have O(V 3 ) total sub-problems. Each sub-problem takes O(V ) time to solve, since we need to consider V possible choices. This gives a total runtime complexity of O(V 4 ). Note that this is no better than |V |× Bellman-Ford 2 Lecture 11 All-Pairs Shortest Paths 6.046J Spring 2015 Bottom-up via relaxation steps 1 for m = 1 to n by 1 2 for u in V 3 for v in V 4 for x in V 5 if duv > dux + dxv 6 duv = dux + dxv In the above pseudocode, we omit superscripts because more relaxation can never hurt. (m) Lm/21 Lm/21 Note that we can change our relaxation step to duv = min(dux +dxv for x ∈ V ). 3 This change would produce an overall running time of O(n lg n) time. (student sug­ gestion) Matrix multiplication Recall the task of standard matrix multiplication, Given n × n matrices A and B, compute C = A · B, such that cij = n k=1 aik · bkj . • O(n3 ) using standard algorithm • O(n2.807 ) using Strassen’s algorithm • O(n2.376 ) using Coppersmith-Winograd algorithm • O(n2.3728 ) using Vassilevska Williams algorithm Connection to shortest paths • Define ⊕ = min and 8 = + • Then, C = A 8 B produces cij = mink (aik + bkj ) (m) • Define D(m) = (dij ), W = (w(i, j)), V = {1, 2, . . . , n} With the above definitions, we see that D(m) can be expressed as D(m−1) 8 W . In other words, D(m) can be expressed as the circle-multiplication of W with itself m times. 3 Lecture 11 6.046J Spring 2015 All-Pairs Shortest Paths Matrix multiplication algorithm • n − 2 multiplications ⇒ O(n4 ) time (stil no better) lg n • Repeated squaring: ((W 2 )2 )2··· = W 2 = W n−1 = (δ(i, j)) if no negativeweight cycles. Time complexity of this algorithm is now O(n3 lg n). We can’t use Strassen, etc. since our new multiplication and addition operations don’t support negation. Floyd-Warshall: Dynamic Programming, attempt 2 (k) 1. Sub-problems: cuv = weight of shortest path u → v whose intermediate vertices ∈ {1, 2, . . . , k} 2. Guessing: Does shortest path use vertex k? 3. Recurrence: (k−1) (k−1) c(k) , cuk uv = min(cuv (k−1) + ckv ) (0) cuv = w(u, v) 4. Topological ordering: for k: for u and v in V : (n) (n) 5. Original problem: δ(u, v) = cuv . Negative weight cycle ⇔ negative cuu Time complexity This Dynamic Program contains O(V 3 ) problems as well. However, in this case, it takes only O(1) time to solve each sub-problem, which means that the total runtime of this algorithm is O(V 3 ). Bottom up via relaxation 1 C = (w(u, v)) 2 for k = 1 to n by 1 3 for u in V 4 for v in V 5 if cuv > cuk + ckv 6 cuv = cuk + ckv As before, we choose to ignore subscripts. 4 Lecture 11 All-Pairs Shortest Paths 6.046J Spring 2015 Johnson’s algorithm 1. Find function h : V → R such that wh (u, v) = w(u, v) + h(u) − h(v) ≥ 0 for all u, v ∈ V or determine that a negative-weight cycle exists. 2. Run Dijkstra’s algorithm on (V, E, wh ) from every source vertex s ∈ V ⇒ get δh (u, v) for all u, v ∈ V 3. Given δh (u, v), it is easy to compute δ(u, v) Claim. δ(u, v) = δh (u, v) − h(u) + h(v) Proof. Look at any u → v path p in the graph G • Say p is v0 → v1 → v2 → · · · → vk , where v0 = u and vk = v. k wh (p) = wh (vi−1 , vi ) i=1 k [w(vi−1 , vi ) + h(vi−1 ) − h(vi )] = i=1 k w(vi−1 , vi ) + h(v0 ) − h(vk ) = i=1 = w(p) + h(u) − h(v) • Hence all u → v paths change in weight by the same offset h(u) − h(v), which implies that the shortest path is preserved (but offset). How to find h? We know that wh (u, v) = w(u, v) + h(u) − h(v) ≥ 0 This is equivalent to, h(v) − h(u) ≤ w(u, v) for all (u, v) ∈ V . This is called a system of difference constraints. Theorem. If (V, E, w) has a negative-weight cycle, then there exists no solution to the above system of difference constraints. 5 Lecture 11 All-Pairs Shortest Paths 6.046J Spring 2015 Proof. Say v0 → v1 → · · · → vk → v0 is a negative weight cycle. Let us assume to the contrary that the system of difference constraints has a solution; let’s call it h. This gives us the following system of equations, h(v1 ) − h(v0 ) ≤ w(v0 , v1 ) h(v2 ) − h(v1 ) ≤ w(v1 , v2 ) .. . h(vk ) − h(vk−1 ) ≤ w(vk−1 , vk ) h(v0 ) − h(vk ) ≤ w(vk , v0 ) Summing all these equations gives us 0 ≤ w(cycle) < 0 which is obviously not possible. From this, we can conclude that no solution to the above system of difference constraints exists if the graph (V, E, w) has a negative weight cycle. Theorem. If (V, E, w) has no negative-weight cycle, then we can find a solution to the difference constraints. Proof. Add a new vertex s to G, and add edges (s, v) of weight 0 for all v ∈ V . • Clearly, these new edges do not introduce any new negative weight cycles to the graph • Adding these new edges ensures that there now exists at least one path from s to v. This implies that δ(s, v) is finite for all v ∈ V • We now claim that h(v) = δ(s, v). This is obvious from the triangle inequality: δ(s, u) + w(u, v) ≥ δ(s, v) ⇔ δ(s, v) − δ(s, u) ≤ w(u, v) ⇔ h(v) − h(u) ≤ w(u, v) Time complexity 1. The first step involves running Bellman-Ford from s, which takes O(V E) time. We also pay a pre-processing cost to reweight all the edges (O(E)) 6 Lecture 11 All-Pairs Shortest Paths 6.046J Spring 2015 2. We then run Dijkstra’s algorithm from each of the V vertices in the graph; the total time complexity of this step is O(V E + V 2 lg V ) 3. We then need to reweight the shortest paths for each pair; this takes O(V 2 ) time. The total running time of this algorithm is O(V E + V 2 lg V ). Applications Bellman-Ford consult any system of difference constraints (or report that it is un­ solvable) in O(V E) time where V = variables and E = constraints. An exercise is to prove the Bellman-Ford minimizes maxi xi − mini xi . This has applications to • Real-time programming • Multimedia scheduling • Temporal reasoning For example, you can bound the duration of an event via difference constraint LB ≤ tend − tstart ≤ U B, or bound a gap between events via 0 ≤ tstart2 − tend1 ≤ ε, or synchronize events via |tstart1 − tstart2 | ≤ ε or 0. 7