6.046J Lecture 6: All-Pairs Shortest Paths I

Lecture 6 All-Pairs Shortest Paths I Supplemental reading in CLRS: Chapter 25 intro; Section 25.2 6.1 Dynamic Programming Like the greedy and divide-and-conquer paradigms, dynamic programming is an algorithmic paradigm in which one solves a problem by combining the solutions to smaller subproblems. In dynamic programming, the subproblems overlap, and the solutions to “inner” problems are stored in memory (see Figure 6.1). This avoids the work of repeatedly solving the innermost problem. Dynamic programming is often used in optimization problems (e.g., finding the maximum or minimum solution to a problem). • The key feature that a problem must have in order to be amenable to dynamic programming is that of optimal substructure: the optimal solution to the problem must contain optimal solutions to subproblems. • Greedy algorithms are similar to dynamic programming, except that in greedy algorithms, the solution to an inner subproblem does not affect the way in which that solution is augmented to the solution of the full problem. In dynamic programming the combining process is more sophisticated, and depends on the solution to the inner problem. • In divide-and-conquer, the subproblems are disjoint. Dynamic Programming Divide-and-Conquer problem subproblem 1 subproblem subsubproblem subproblem 2 subproblem 3 problem Figure 6.1. Schematic diagrams for dynammic programming and divide-and-conquer. 6.2 Shortest-Path Problems Given a directed graph G = (V , E, w) with real-valued edge weights, it is very natural to ask what the shortest (i.e., lightest) path between two vertices is. Input: A weighted, directed graph G = (V , E, w) with real-valued edge weights, a start vertex u, and an end vertex v Output: The minimal weight of a path from u to v. That is, the value of n o ( p min w(p) : paths u v if such a path exists δ(u, v) = ∞ otherwise, where the weight of a path p = 〈v0 , v1 , . . . , vk 〉 is w(p) = k X w(v i−1 , v i ). i =1 (Often we will also want an example of a path which achieves this minimal weight.) Shortest paths exhibit an optimal-substructure property: Proposition 6.1 (Theorem 24.1 of CLRS). Let G = (V , E, w) be a weighted, directed graph with realvalued edge weights. Let p = 〈v0 , v1 , . . . , vk 〉 be a shortest path from v0 to vk . Let i, j be indices with ­ ® 0 ≤ i ≤ j ≤ k, and let p i j be the subpath v i , v i+1 , . . . , v j . Then p i j is a shortest path from v i to v j . Proof. We are given that p : v0 p 0i / vi pi j / vj p jk / vk is a shortest path. If there were a shorter path from v i to v j , say v i obtain a shorter path from v0 to vk : 0 p : v0 p 0i / vi p0i j / vj p jk p0i j v j , then we could patch it in to / vk , which is impossible. 6.2.1 All Pairs In recitation, we saw Dijkstra’s algorithm (a greedy algorithm) for finding all shortest paths from a single source, for graphs with nonnegative edge weights. In this lecture, we will solve the problem of finding the shortest paths between all pairs of vertices. This information is useful in many contexts, such as routing tables for courier services, airlines, navigation software, Internet traffic, etc. The simplest way to solve the all-pairs shortest path problem is to run Dijkstra’s algorithm |V | times, once with each vertex as the source. This would take time |V |· T D IJKSTRA , which, depending on the implementation of the min-priority queue data structure, would be ¡ ¢ ¡ ¢ Linear array: O V3 +VE = O V3 ¡ ¢ Binary min-heap: O V E lg V ¡ ¢ Fibonacci heap: O V 2 lg V + V E . Lec 6 – pg. 2 of 5 However, Dijkstra’s algorithm only works if the edge weights are nonnegative. If we wanted to allow negative edge weights, we could instead use the slower Bellman–Ford algorithm once per vertex: ¡ ¢ dense graph ¡ ¢ O V 2 E −−−−−−−−→ O V 4 . We had better be able to beat this! 6.2.2 Formulating the All-Pairs Problem When we solved the single-source shortest paths problem, the shortest paths were represented on the actual graph, which was possible because subpaths of shortest paths are shortest paths and because there was only one source. This time, since we are considering all possible source vertices at once, it is difficult to conceive of a graphical representation. Instead, we will use matrices. Let n = |V |, and arbitrarily label the vertices 1, 2, . . . , n. We will format the output of the all-pairs ¡ ¢ algorithm as an n × n distance matrix D = d i j , where ( d i j = δ(i, j) = weight of a shortest path from i to j if a path exists ∞ if no path exists, ¡ ¢ together with an n × n predecessor matrix Π = π i j , where ( πi j = if i = j or there is no path from i to j N IL, predecessor of j in our shortest path i j otherwise. Thus, the ith row of Π represents the sinlge-source shortest paths starting from vertex i, and the ith ¡ ¢ row of D gives the weights of these paths. We can also define the weight matrix W = w i j , where ( wi j = weight of edge (i, j) if edge exists ∞ otherwise. Because G is a directed graph, the matrices D, Π and W are not necessarily symmetric. The existence of a path from i to j does not tell us anything about the existence of a path from j to i. 6.3 The Floyd–Warshall Algorithm The Floyd–Warshall algorithm solves the all-pairs shortest path problem in Θ(V 3 ) time. It allows negative edge weights, but assumes that there are no cycles with negative total weight.1 The Floyd– Warshall algorithm uses dynamic programming based on the following subproblem: What are D and Π if we require all paths to have intermediate vertices2 taken from the © ª © ª set 1, . . . , k , rather than the full 1, . . . , n ? 1 If there were a negative-weight cycle, then there would exist paths of arbitrarily low weight, so some vertex pairs would have a distance of −∞. In particular, the distance from a vertex to itself would not necessarily be zero, so our algorithms would need some emendations. 2 An intermediate vertex in a path p = 〈v , . . . , v 〉 is one of the vertices v , . . . , v n 0 1 n−1 , i.e., not an endpoint. Lec 6 – pg. 3 of 5 1 1 2 2 i i 3 3 j j k k Figure 6.2. Either p passes through vertex k, or p doesn’t pass through vertex k. As k increases from 0 to n, we build up the solution to the all-pairs shortest path problem. The base case k = 0 (where no intermediate vertices are allowed) is easy: ³ ´ ³ ´ (0) D (0) = d i j and Π(0) = π(0) ij , where ( d (0) ij = 0 if i = j wi j otherwise ) ( π(0) ij and = N IL if i = j or w i j = ∞ i if i 6= j and there is an edge from i to j ) . In general, let D (k) and Π(k) be the corresponding matrices when paths are required to have all their intermediate vertices taken from the set {1, . . . , k}. (Thus D = D (n) and Π = Π(n) .) What we need is a way of computing D (k) and Π(k) from D (k−1) and Π(k−1) . The following observation provides just that. Observation. Let p be a shortest path from i to j when we require all intermediate vertices to come from {1, . . . , k}. Then either k is an intermediate vertex or k is not an intermediate vertex. Thus, one of the following: 1. k is not an intermediate vertex of p. Thus, p is also a shortest path from i to j when we require all intermediate vertices to come from {1, . . . , k − 1}. 2. k is an intermediate vertex for p. Thus, we can decompose p as p: i p ik /k pk j / j, where p ik and p k j are shortest paths when we require all intermediate vertices to come from {1, . . . , k − 1}, by (a slightly modified version of) Proposition 6.1. This tells us precisely that ( d (k) ij = wi j min if k = 0 ³ −1) d (k , ij −1) −1) d (k + d (k ik kj Thus we may compute D by the following procedure: Lec 6 – pg. 4 of 5 ´ if k ≥ 1. Algorithm: F LOYD –WARSHALL(W) ¯ ¯ 1 n ← ¯W.rows¯ 2 3 4 5 6 7 8 9 D (0) ← W Π(0) ← an n × n matrix with all entries initially N IL for k ← 1 to n do ³ ´ ³ ´ (k) (k) Let D (k) = d i j and Π(k) = π i j be new n × n matrices for i ← 1 to n do for j ← 1 to n do ³ ´ (k−1) (k−1) (k−1) d (k) ← min d , d + d ij ij ik kj −1) −1) if d (k) ≤ d (k + d (k then ij ik kj −1) π(k) ← π(k ij ij 10 11 12 else −1) π(k) ← π(k ij kj ¡ ¢ Being in a triply nested loop, lines 8–12 are executed n3 times. Thus, the algorithm runs in Θ n3 = ¡ ¢ ¡ ¢ Θ V 3 time. Note that while the algorithm as written requires Θ V 3 space, reasonable implementa¡ 2¢ tions will only require Θ V space: we only ever need to memorize four matrices at a time, namely D (k) , D (k−1) , Π(k) , Π(k−1) . In fact, we can get away with memorizing even less—see Exercise 25.2-4 of CLRS. Lec 6 – pg. 5 of 5