6.046J Lecture 7: All-Pairs Shortest Paths II

Lecture 7 All-Pairs Shortest Paths II Supplemental reading in CLRS: Section 25.3 7.1 Johnson’s Algorithm ¡ ¢ The Floyd–Warshall algorithm runs in Θ V 3 time. Recall that, if all edge weights are nonnegative, then repeated application of Dijkstra’s algorithm using a Fibonacci heap gives the all-pairs shortest ¡ ¢ paths in Θ V 2 lg V + V E time. If G is not dense (i.e., if |E | is not on the order of |V |2 ), then Dijkstra’s algorithm asymptotically outperforms the Floyd–Warshall algorithm. So our goal for the first half of this lecture will be to reduce the problem of finding all-pairs shortest paths on an arbitrary graph to that of finding all-pairs shortest paths on a graph with nonnegative edge weights. 7.1.1 Reweighting How might we “eliminate” negative edge weights? The naïve way would be to add some constant N to all the edge weights, where N is chosen large enough to make all the edge weights nonnegative. Unfortunately, this transformation does not preserve shortest paths. Given a path p : P 〈 u = v0 , v1 , . . . , vk = v〉 from u to v with total weight w(p) = ki=1 w(v i−1 , v i ), the weight of p in the new graph would be w(p) + kN. Thus, a very light path in the original graph might not be so attractive in the new graph, if it contained lots of edges (see Figure 7.1). We will need to do something smarter; the change in weight must vary from edge to edge. Our goal is to assign to each edge (u, v) a new weight w(u, b v), such that the new weight function w b has the following two properties: 1. For each pair of vertices u, v ∈ V and each path p : u v, the old weight w(p) is minimal if and only if the new weight w(p) b is minimal (among paths from u to v). 2. For all edges (u, v), the new weight w(u, b v) is nonnegative. −4 −4 −5 1 1 0 Figure 7.1. Adding a constant to the weight of every edge does not preserve shortest paths. A clever, simple solution to this problem is as follows. Let h : V → R be a scalar-valued function on the vertices. Assign w(u, b v) = w(u, v) + h(v) − h(u). This weighting has the property that, for a path p : 〈 u = v0 , v1 , . . . , vk = v〉, the new weight is w(p) b = = k X i =1 k X w b (v i−1 , v i ) w (v i−1 , v i ) + h (v i ) − h (v i−1 ) i =1 = w(p) + k X h (v i ) − h (v i−1 ) i =1 = w(p) + h (vk ) − h (v0 ) = w(p) + h(v) − h(u), by telescoping. Thus, the amount by which p changes depends only on the endpoints u and v, not on the intermediate vertices. Consequently, a path p : u v is minimal with respect to w b if and only if it is minimal with respect to w. Also, if u = v, then w(p) b = w(p), so the weight of cycles is unchanged. Thus, negative-weight cycles are preserved, so the distance from u to v with respect to w b is −∞ if and only if the distance from u to v with respect to w is −∞. Our task now is to choose an appropriate function h so that the edge wieghts w b become nonnegative. There is a magical answer to this question: Let s be a new vertex, and construct an augmented graph G 0 = (V 0 , E 0 ) with V 0 = V ∪{ s}. Take E 0 to consist of all the edges in E, plus a directed edge from s to each vertex in V (see Figure 7.2). Then let h(v) = −δ(s, v), where δ(s, v) is the weight of the shortest path from s to v. Note that Proposition 6.1 implies the “triangle inequality” δ(s, v) ≤ δ(s, u) + δ(u, v) (with equality if one of the shortest paths from s to v passes through u). Since δ(u, v) ≤ w(u, v), we have δ(s, v) ≤ δ(s, u) + w(u, v). Hence w(u, b v) = w(u, v) + h(v) − h(u) = w(u, v) − δ(s, v) + δ(s, u) ¡ ¢ ≥ w(u, v) − δ(s, u) + w(u, v) + δ(s, u) = 0. Applying the weights w b to G, we obtain the following algorithm, due to Johnson: Lec 7 – pg. 2 of 7 0 0 3 4 8 0 7 1 s 2 −4 −5 0 6 0 Figure 7.2. The augmented graph G 0 in Johnson’s algorithm, consisting of G together with a special vertex s from which there emanates an edge of weight 0 to each other vertex. Algorithm: J OHNSON(G) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Construct the augmented graph G 0 , where G 0 .V = G.V ∪ { s} and G 0 .E = G.E ∪ © ª (s, v) with G 0 .w(s, v) = 0, for each v ∈ G.V if B ELLMAN –F ORD(G 0 , s) = FALSE then B if B ELLMAN –F ORD complains about a negative-weight cycle error “The input graph contians a negative-weight cycle.” else for each vertex v ∈ G.V do Set h(v) ← −δ(s, v), where δ(s, v) is as computed by B ELLMAN –F ORD for each edge (u, v) ∈ G.E do w(u, b v) ← G.w(u, v) + h(v) − h(u) ¡ ¢ ¡ ¢ Let D = d uv and Π = πuv be new n × n matrices for each vertex u ∈ G.V do Run D IJKSTRA(G, w, b u) to compute δb(u, v) for all v ∈ G.V for each vertex v ∈ G.V do B correct the shortest path weights ¡ ¢ d uv ← δb(u, v) − h(v) − h(u) πuv ← the predecessor of v as computed by D IJKSTRA(G, w, b u) above return D The only steps in this algorithm that take more than O(E) time are the call to B ELLMAN –F ORD on line 2 (which takes Θ(V E) time) and the |V | calls to D IJKSTRA on lines 11–16 (each of which ¡ ¢ takes Θ V lg V + E time using a Fibonacci heap). Thus, the total running time of J OHNSON is ¡ 2 ¢ Θ V lg V + V E . Lec 7 – pg. 3 of 7 7.2 Linear Programming Linear programming is a very general class of problem that arises frequently in diverse fields. The goal is to optimize a linear objective function subject to linear constraints (equalities and inequalities). That is, we want to maximize or minimize the function n X f (x1 , x2 , . . . , xn ) = a 1 x1 + a 2 x2 + · · · + a n xn = a jxj j =1 subject to the constraints (i) (i) g(i) (x1 , . . . , xn ) = b(i) 1 x1 + b 2 x2 + · · · + b n x n = and (i) (i) h(i) (x1 , . . . , xn ) = c(i) 1 x1 + c 2 x2 + · · · + c n x n = n X j =1 n X j =1 b(i) x j = p(i) j c(i) x j ≤ q(i) . j In vector form, we want to maximize or minimize aT x subject to the constraints Bx = p and Cx ≤ q (meaning that the ith entry of Cx is less than or equal to the ith entry of q for every i). Here B and C are matrices with n columns (and any number of rows). 7.2.1 Application: Bacterial Growth One of the many applications of linear programming is the problem of maximizing bacterial growth subject to biochemical constraints. Consider the transport pathways of a bacterial cell, which we model as a graph embedded in three-dimensional space (see Figure 7.3). Let x i be the flux through edge i. • At steady-state, the net flux through each vertex of the graph is zero, as wastes are not building up along the cell pathways. This amounts to a linear constraint at each vertex, e.g., x1 − x2 − x3 = 0 in the picture. • Each edge has a minimum (namely zero) and a maximum rate at which molecules can pass (i) through. This amounts to a linear constraint 0 ≤ x i ≤ vmax at each edge. • The objective function is the sum of fluxes contributing to biomass production (e.g., synthesis of amino acids and proteins). The availability of efficient solutions to linear programming problems has been valuable in the engineering of new bacterial strains with improved capabilities, e.g., to produce biofuels. Lec 7 – pg. 4 of 7 Food source Zoom in on a vertex: x1 x2 x3 Flow constraint: x1 − x2 − x3 = 0 Figure 7.3. Bacterial cell, with a graph representing its transport pathways. At steady-state, the net flux through each vertex is zero. 7.2.2 Difference Constraints as Graphs It turns out that shortest path problems are related to some forms of linear programming problems. Consider a system of linear constraints, each having the form x j − xi ≤ b k , in other words, a system of the form Ax ≤ b, where A is an m × n matrix, x is an n-dimensional vector and b is an m-dimensional vector, and where each row of A contains one 1, one −1, and all other entries are zero. As a concrete example, let’s consider the system     1 −1 0 0   0 x1  1  0 0 −1   −1      x2    1 0 −1   ≤  1  . 0    x3    5 −1 0 1 0 x4 −3 0 0 −1 1 This is equalivalent to the inequalities   x1 − x2 ≤ 0             x − x ≤ − 1 1 4     x2 − x4 ≤ 1 .        x3 − x1 ≤ 5          x4 − x3 ≤ −3 Lec 7 – pg. 5 of 7 0 v1 v2 0 0 v0 −1 5 1 0 v4 −3 v3 0 Figure 7.4. Constraint graph for the system of difference constraints Ax ≤ b, where A and b are as in our example. Two plausible solutions to this system are  −5 −3   x =  , 0 −4    0 2   x =  . 5 1 In general, it’s not hard to see that adding any multiple of (1, 1, 1, 1)T to a solution produces another solution. Let’s now construct a graph G, called the constraint graph for this system (see Figure 7.4). The © ª vertex set of G is V = v0 , . . . , vn . Draw a directed edge with weight 0 from v0 to each other vertex. Then, for each difference constraint x j − x i ≤ b, draw an edge from v i to v j with weight b. Theorem 7.1 (Theorem 24.9 of CLRS). Given a system Ax ≤ b of difference constraints, let G = (V , E) be the corresponding constraint graph. If G contians no negative-weight cycles, then   δ (v0 , v1 )    δ (v0 , v2 )    x= ..  .   δ (v0 , vn ) is a feasible solution. If G does contain negative-weight cycles, then there is no feasible solution. Proof. Assume there are no negative-weight cycles. Since shortest paths satisfy the triangle inequality, we have ¡ ¢ ¡ ¢ δ v0 , v j ≤ δ (v0 , v i ) + w v i , v j . | {z } | {z } | {z } xj xi b Rearranging, we obtain x j − x i ≤ b. Next, consider the case of a negative-weight cycle. Without loss of generality, assume the cycle is ­ ® of the form c = v1 , v2 , . . . , vk , v1 . Then any solution x to the system of difference constraints must satisfy Lec 7 – pg. 6 of 7 x2 − x1 x3 − x2 + xk − xk−1 x1 − xk 0 ≤ ≤ .. . ≤ ≤ ≤ w (v1 , v2 ) w (v2 , v3 ) w (vk−1 , vk ) w (vk , v1 ) w(c) < 0, a contradiction. Therefore there cannot be any solutions to the system of difference constraints. Lec 7 – pg. 7 of 7