Analysis of Algorithms, I CSOR W4231.002 Eleni Drinea Computer Science Department Columbia University Tuesday, March 10, 2015 Outline 1 Recap 2 Graphs with negative edge weights: why Dijkstra fails 3 Single-source shortest paths (negative edges): Bellman-Ford A DP solution An alternative formulation of the algorithm 4 All-pairs shortest paths (negative edges): Floyd-Warshall Today 1 Recap 2 Graphs with negative edge weights: why Dijkstra fails 3 Single-source shortest paths (negative edges): Bellman-Ford A DP solution An alternative formulation of the algorithm 4 All-pairs shortest paths (negative edges): Floyd-Warshall Review of the last lecture I Connectivity in graphs I I I Undirected: find connected components via BFS or DFS Directed: find strongly connected components via DFS Single-source shortest paths in directed weighted graphs with non-negative edge weights I I Dijkstra’s algorithm computes shortest path distances from a vertex s to every other vertex in the graph Best implementation depends on the density of the graph Today 1 Recap 2 Graphs with negative edge weights: why Dijkstra fails 3 Single-source shortest paths (negative edges): Bellman-Ford A DP solution An alternative formulation of the algorithm 4 All-pairs shortest paths (negative edges): Floyd-Warshall Example graph with negative edge weights 2 a 1 c s 5 b -4 Dijkstra’s output and correct output for example graph (2) 2 a s 5 b (5) 1 (3) c 2 (2) a (1) c s 5 b -4 (5) Dijkstra’s algorithm will first include a to S and then c, thus missing the shorter path from s to b to c. Negative edge weights: why Dijkstra’s algorithm fails I Intuitively, a path may start on expensive edges but then compensate along the way with cheap edges. I Formally, in the proof of correctness of the algorithm, the last statement about P does not hold anymore: even if the cost (weight) of path Pv is smaller than the cost of the subpath s → x → y, negative edges on the subpath y → v may now result in P being cheaper than Pv . Bigger problems in graphs with negative edges? 2 a 1 s 5 b dist(a) =? c 1 -4 Bigger problems in graphs with negative edges? 2 a 1 s c 1 5 b -4 1. dist(v) goes to −∞ for every v on the cycle 2. no solution to shortest paths when negative cycles ⇒ need to detect negative cycles Today 1 Recap 2 Graphs with negative edge weights: why Dijkstra fails 3 Single-source shortest paths (negative edges): Bellman-Ford A DP solution An alternative formulation of the algorithm 4 All-pairs shortest paths (negative edges): Floyd-Warshall Single-source shortest paths, negative edge weights Input: weighted directed graph G = (V, E, w), w : E → R; a source (origin) vertex s ∈ V Output: I I Decide if G has a negative cycle If no negative cycles 1. find the costs (weights) of shortest s-v paths for all v ∈ V 2. reconstruct shortest s-v paths Properties of shortest paths Suppose the problem has a solution for an input graph. I Can there be negative cycles in the graph? I Can there be positive cycles in the graph? I Can the shortest paths contain positive cycles? I Consider a shortest s-t path; are its subpaths shortest? Towards a DP solution Key observation: if there are no negative cycles, a path cannot become cheaper by traversing a cycle. Fact 1. If G has no negative cycles, then there is a shortest s-v path that is simple, thus has at most n − 1 edges. Fact 2. The shortest paths problem exhibits optimal substructure. Facts 1 and 2 suggest a DP solution. Subproblems w s v Let OP T (i, v) = cost of a shortest s-v path with at most i edges Consider a shortest s-v path using at most i edges. I If the path uses at most i − 1 edges, then OP T (i, v) = OP T (i − 1, v). I If the path uses i edges, then OP T (i, v) = min x:(x,v)∈E {OP T (i − 1, x) + w(x, v)} . Subproblems and recurrence Let OP T (i, v) = cost of a shortest s-v path using at most i edges Then 0, ∞, ( OP T (i, v) = min if i = 0, v = s if i = 0, v 6= s OP T (i − 1, v) min {OP T (i − 1, x) + w(x, v)}, x:(x,v)∈E if i > 0 Example of Bellman-Ford Compute shortest s-v paths in the graph below, for all v ∈ V . a 4 s -1 1 c 2 5 b -1 Pseudocode n × n dynamic programming table M storing OP T (i, v) Bellman-Ford(G = (V, E, w), s ∈ V ) for v ∈ V do M [0, v] = ∞ end for M [0, s] = 0 for i = 1, . . . , n − 1 do for v ∈ V (in any order) do M [i −n1, v] o M [i, v] = min min M [i − 1, x] + w(x, v) x:(x,v)∈E end for end for Running time & Space I Running time: O(nm) I Space: Θ(n2 ) —can be improved (coming up) I To reconstruct actual shortest paths: keep array prev of size n such that prev[v] = predecessor of v in current shortest s-v path. Improving space requirements Only need two columns of M at all times. 4 Actually, only need one! (see Remark 1) Thus drop the index i from M [i, v] and only use it as a counter for #repetitions. n o M [v] = min M [v], min M [x] + w(x, v) x:(x,v)∈E Remark 1. Throughout the algorithm, M [v] is the cost of some s-v path. After i repetitions, M [v] is no larger than the cost of the current shortest s-v path with at most i edges. Early termination condition: if at some iteration i no value in M changed, then stop (why?) –also allows to detect negative cycles. An alternative way to view Bellman-Ford s v1 v2 … vk-1 v I Let P = (s = v0 , v1 , v2 , . . . , vk = v) be a shortest s-v path. I Then P can contain at most n − 1 edges. I How can we correctly compute dist(v) on this path? Key observations about subroutine Update(u, v) Recall subroutine Update from Dijkstra’s algorithm: Update(u, v) : dist(v) = min{dist(v), dist(u) + w(u, v)} Fact 3. Suppose u is the last node on the shortest s-v path, and suppose dist(u) has been correctly set. The call Update(u, v) returns the correct value for dist(v). Fact 4. No matter how many times Update(u, v) is performed, it will never make dist(v) too small. That is, Update is a safe operation: performing few extra updates can’t hurt. Main idea Suppose we update the edges on the shortest path P in the order they appear on the path (though not necessarily consecutively). Hence we update (s, v1 ), (v1 , v2 ), (v2 , v3 ), . . . , (vk−1 , v) This sequence of updates correctly computes dist(v1 ), dist(v2 ), . . ., dist(v) (by induction and Fact 3). How can we guarantee that updates will happen in this order? Bellman-Ford algorithm Update all m edges in the graph, n − 1 times in a row. I By Fact 4, it is ok to update an edge several times in between. I All we care for is that the edges on the path are updated in this particular order. This is guaranteed if we update all edges n − 1 times in a row. Pseudocode We will use Initialize and Update from Dijkstra’s algorithm. Initialize(G, s) for v ∈ V do dist[v] = ∞ prev[v] = N IL end for dist[s] = 0 Update(u, v) if dist[v] > dist[u] + w(u, v) then dist[v] = dist[u] + w(u, v) prev[v] = u end if Bellman-Ford Bellman-Ford(G = (V, E, w), s) Initialize(G, s) for i = 1, . . . , n − 1 do for (u, v) ∈ E do Update(u, v) end for end for Running time? Space? Detecting negative cycles 2 a 1 s c 1 5 b -4 1. dist(v) goes to −∞ for every v on the cycle. 2. Any shortest s-v path can have at most n − 1 edges. 3. Update every edge n times (instead of n − 1): if dist(v) changes for any v ∈ V , there is a negative cycle. Today 1 Recap 2 Graphs with negative edge weights: why Dijkstra fails 3 Single-source shortest paths (negative edges): Bellman-Ford A DP solution An alternative formulation of the algorithm 4 All-pairs shortest paths (negative edges): Floyd-Warshall All pairs shortest-paths I Input: a directed graph G with real edge weights I Output: an n × n matrix D such that D[i, j] = weight of shortest path from i to j Solving all pairs shortest-paths 1. Straightforward solution: run Bellman–Ford once for every vertex (O(n2 m) time). 2. Improved solution: a dynamic programming algorithm for generating shortest paths (Floyd–Warshall, O(n3 ) time). Towards a DP formulation I Consider a shortest path P from s to t. I This path uses some intermediate vertices: that is, if P = (s, v1 , v2 , . . . , vk , t), then v1 , . . . , vk are intermediate vertices. I For simplicity, let V = {1, 2, 3, . . . , n} and consider a shortest path from i to j when intermediate vertices may only be from {1, 2, . . . , k}. I Goal: find the shortest i-j path using {1, 2, . . . , n} as intermediate vertices. Example a 4 s -1 1 c 2 5 b -1 Rename {s, a, b, c} as {1, 2, 3, 4} 2 4 1 -1 1 2 5 3 4 -1 Examples of shortest paths Shortest (1, 2)-path may use: (i) no intermediate nodes (P); or (ii) node 3 (P1) P 1 1 P1 5 4 2 P1 Shortest (1, 3)-path may use: (i) no intermediate nodes (P); or (ii) node 2 (P1) 2 4 3 2 4 -1 1 P1 P1 1 5 -1 P 3 4 A shortest i-j path using nodes from {1, . . . , k} Consider a shortest path P from i to j where intermediate nodes may only be from the set of nodes {1, 2, . . . , k}. i Fact: any subpath of P must be shortest itself. j A useful observation Focus on the last node k from this set. Either 1. P completely avoids k: then a shortest i-j path with intermediate nodes from {1, . . . , k} is the same as a shortest i-j path with intermediate nodes from {1, . . . , k − 1}. 2. Or, k is an intermediate node of P . k i j Decompose P into an i-k subpath P1 and a k-j subpath P2 . i. P1 , P2 are shortest subpaths themselves. ii. All intermediate nodes of P1 , P2 are from {1, . . . , k − 1}. Subproblems Let OP Tk (i, j) = cost of shortest i − j path P using {1, . . . , k} as intermediate vertices 1. Either k does not appear in P , hence OP Tk (i, j) = OP Tk−1 (i, j) 2. Or, k appears in P , hence OP Tk (i, j) = OP Tk−1 (i, k) + OP Tk−1 (k, j) Recurrence Hence w(i, j) OP Tk (i, j) = OP Tk−1 (i, j) min OP Tk−1 (i, k) + OP Tk−1 (k, j) We want OP Tn (i, j). Time/space requirements? , if k = 0 , if k ≥ 1 Floyd-Warshall on example graph D0 = 0 ∞ ∞ ∞ 4 0 2 ∞ 5 -1 0 ∞ ∞ 1 -1 0 D2 = 0 ∞ ∞ ∞ 4 0 2 ∞ 3 -1 0 ∞ 5 1 -1 0 D1 = 0 ∞ ∞ ∞ 4 0 2 ∞ 5 -1 0 ∞ ∞ 1 -1 0 D3 = 0 ∞ ∞ ∞ 4 0 2 ∞ 3 -1 0 ∞ 2 -2 -1 0 Space requirements I A single n × n dynamic programming table D, initialized to w(i, j) (the adjacency matrix of G). I Let {1, . . . , k} be the set of intermediate nodes that may be used for the shortest i-j path. I After the k-th iteration, D[i, j] contains the cost of an i-j path that is no larger than the cost of the shortest i-j path using {1, . . . , k} as intermediate nodes. The Floyd-Warshall algorithm Floyd-Warshall(G = (V, E, w)) for k = 1 to n do for i = 1 to n do for j = 1 to n do D[i, j] = min(D[i, j], D[i, k] + D[k, j]) end for end for end for I Running time: O(n3 ) I Space: Θ(n2 )

© Copyright 2018