Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 18 Prof. Erik Demaine Introduction to Algorithms Day 31 L18.2? 2001 by Charles E. Leiserson Negative-weight cycles Recall: If a graph G = (V, E) contains a negative- weight cycle, then some shortest paths may not exist. Example: u u v v … < 0 Bellman-Ford algorithm: Finds all shortest-path lengths from a source s ∈ V to all v ∈ V or determines that a negative-weight cycle exists. Introduction to Algorithms Day 31 L18.3? 2001 by Charles E. Leiserson Bellman-Ford algorithm d[s] ← 0 for each v ∈ V –{s} do d[v] ←∞ for i ← 1 to |V| –1 do for each edge (u, v) ∈ E do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) for each edge (u, v) ∈ E do if d[v] > d[u] + w(u, v) then report that a negative-weight cycle exists initialization At the end, d[v] = δ(s, v). Time = O(VE). relaxation step Introduction to Algorithms Day 31 L18.4? 2001 by Charles E. Leiserson Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 ABCDE 0 ∞∞∞∞ ∞ 0 ∞ ∞∞ Introduction to Algorithms Day 31 L18.5? 2001 by Charles E. Leiserson ∞–1 0–1∞∞∞ Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 ABCDE 0 ∞∞∞∞ 0 ∞ ∞∞ Introduction to Algorithms Day 31 L18.6? 2001 by Charles E. Leiserson ∞–1 0–1∞∞∞ Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 ABCDE 0 ∞∞∞∞ 0 ∞ ∞4 0–14∞∞ Introduction to Algorithms Day 31 L18.7? 2001 by Charles E. Leiserson 4 0–12∞∞ 2 ∞–1 0–1∞∞∞ Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 ABCDE 0 ∞∞∞∞ 0 ∞ ∞ 0–14∞∞ Introduction to Algorithms Day 31 L18.8? 2001 by Charles E. Leiserson ∞–1 Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 0 ∞ ∞2 0–12∞∞ 0–1∞∞∞ ABCDE 0 ∞∞∞∞ 0–14∞∞ Introduction to Algorithms Day 31 L18.9? 2001 by Charles E. Leiserson ∞–1 Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 0 ∞2 0–12∞∞ 0–1∞∞∞ ABCDE 0 ∞∞∞∞ 0–14∞∞ 1 0–12∞ 1 Introduction to Algorithms Day 31 L18.10? 2001 by Charles E. Leiserson ∞ 0–12 1 1 1 ∞–1 Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 0 2 0–12∞∞ 0–1∞∞∞ ABCDE 0 ∞∞∞∞ 0–14∞∞ 1 0–12∞ 1 Introduction to Algorithms Day 31 L18.11? 2001 by Charles E. Leiserson 1 0–12–21 –2 0–12 1 1 ∞–1 Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 0 2 0–12∞∞ 0–1∞∞∞ ABCDE 0 ∞∞∞∞ 0–14∞∞ 1 0–12∞ 1 Introduction to Algorithms Day 31 L18.12? 2001 by Charles E. Leiserson 1 0–12–21 –2 0–12 1 1 ∞–1 Example of Bellman-Ford A B E C D –1 4 1 2 –3 2 5 3 0 2 0–12∞∞ 0–1∞∞∞ ABCDE 0 ∞∞∞∞ 0–14∞∞ 1 0–12∞ 1 Note: Values decrease monotonically. Introduction to Algorithms Day 31 L18.13? 2001 by Charles E. Leiserson Correctness Theorem. If G = (V, E) contains no negative- weight cycles, then after the Bellman-Ford algorithm executes, d[v] = δ(s, v) for all v ∈ V. Proof. Let v ∈ V be any vertex, and consider a shortest path p from s to v with the minimum number of edges. v 1 v 1 v 2 v 2 v 3 v 3 v k v k v 0 v 0 … s v p: Since p is a shortest path, we have δ(s, v i ) = δ(s, v i–1 ) + w(v i–1 , v i ) . Introduction to Algorithms Day 31 L18.14? 2001 by Charles E. Leiserson Correctness (continued) v 1 v 1 v 2 v 2 v 3 v 3 v k v k v 0 v 0 … s v p: Initially, d[v 0 ] = 0 = δ(s, v 0 ), and d[s] is unchanged by subsequent relaxations (because of the lemma from Lecture 17 that d[v] ≥δ(s, v)). ? After 1 pass through E, we have d[v 1 ] = δ(s, v 1 ). ? After 2 passes through E, we have d[v 2 ] = δ(s, v 2 ). M ? After k passes through E, we have d[v k ] = δ(s, v k ). Since G contains no negative-weight cycles, p is simple. Longest simple path has ≤ |V| –1edges. Introduction to Algorithms Day 31 L18.15? 2001 by Charles E. Leiserson Detection of negative-weight cycles Corollary. If a value d[v] fails to converge after |V| –1passes, there exists a negative-weight cycle in G reachable from s. Introduction to Algorithms Day 31 L18.16? 2001 by Charles E. Leiserson DAG shortest paths If the graph is a directed acyclic graph (DAG), we first topologically sort the vertices. Walk through the vertices u ∈ V in this order, relaxing the edges in Adj[u], thereby obtaining the shortest paths from s in a total of O(V + E) time. ? Determine f : V → {1, 2, …, |V|} such that (u, v) ∈ E ? f (u) < f (v). ? O(V + E) time using depth-first search. 3 3 5 5 6 6 4 4 2 2 s 7 7 9 9 8 81 1 Introduction to Algorithms Day 31 L18.17? 2001 by Charles E. Leiserson Linear programming Let A be an m×n matrix, b be an m-vector, and c be an n-vector. Find an n-vector x that maximizes c T x subject to Ax ≤ b, or determine that no such solution exists. . ≤ . maximizing m n Ax≤ bc T x Introduction to Algorithms Day 31 L18.18? 2001 by Charles E. Leiserson Linear-programming algorithms Algorithms for the general problem ? Simplex methods — practical, but worst-case exponential time. ? Ellipsoid algorithm — polynomial time, but slow in practice. ? Interior-point methods — polynomial time and competes with simplex. Feasibility problem: No optimization criterion. Just find x such that Ax ≤ b. ? In general, just as hard as ordinary LP. Introduction to Algorithms Day 31 L18.19? 2001 by Charles E. Leiserson Solving a system of difference constraints Linear programming where each row of A contains exactly one 1, one –1, and the rest 0’s. Example: x 1 – x 2 ≤ 3 x 2 – x 3 ≤ –2 x 1 – x 3 ≤ 2 x j – x i ≤ w ij Solution: x 1 = 3 x 2 = 0 x 3 = 2 Constraint graph: v j v j v i v i x j – x i ≤ w ij w ij (The “A” matrix has dimensions |E| × |V|.) Introduction to Algorithms Day 31 L18.20? 2001 by Charles E. Leiserson Unsatisfiable constraints Theorem. If the constraint graph contains a negative-weight cycle, then the system of differences is unsatisfiable. Proof. Suppose that the negative-weight cycle is v 1 → v 2 → L → v k → v 1 . Then, we have x 2 – x 1 ≤ w 12 x 3 – x 2 ≤ w 23 M x k – x k–1 ≤ w k–1, k x 1 – x k ≤ w k1 Therefore, no values for the x i can satisfy the constraints. 0 ≤ weight of cycle < 0 Introduction to Algorithms Day 31 L18.21? 2001 by Charles E. Leiserson Satisfying the constraints Theorem. Suppose no negative-weight cycle exists in the constraint graph. Then, the constraints are satisfiable. Proof. Add a new vertex s to V with a 0-weight edge to each vertex v i ∈ V. v 1 v 1 v 4 v 4 v 7 v 7 v 9 v 9 v 3 v 3 s 0 Note: No negative-weight cycles introduced ? shortest paths exist. Introduction to Algorithms Day 31 L18.22? 2001 by Charles E. Leiserson The triangle inequality gives us δ(s,v j ) ≤δ(s, v i ) + w ij . Since x i = δ(s, v i ) and x j = δ(s, v j ), the constraint x j – x i ≤ w ij is satisfied. Proof (continued) Claim: The assignment x i = δ(s, v i ) solves the constraints. s s v j v j v i v i δ(s, v i ) δ(s, v j ) w ij Consider any constraint x j – x i ≤ w ij , and consider the shortest paths from s to v j and v i : Introduction to Algorithms Day 31 L18.23? 2001 by Charles E. Leiserson Bellman-Ford and linear programming Corollary. The Bellman-Ford algorithm can solve a system of m difference constraints on n variables in O(mn) time. Single-source shortest paths is a simple LP problem. In fact, Bellman-Ford maximizes x 1 + x 2 + L + x n subject to the constraints x j – x i ≤ w ij and x i ≤ 0 (exercise). Bellman-Ford also minimizes max i {x i } – min i {x i } (exercise). Introduction to Algorithms Day 31 L18.24? 2001 by Charles E. Leiserson Application to VLSI layout compaction Integrated -circuit features: Problem: Compact (in one dimension) the space between the features of a VLSI layout without bringing any features too close together. minimum separation λ Introduction to Algorithms Day 31 L18.25? 2001 by Charles E. Leiserson VLSI layout compaction 1 1 x 1 x 2 2 d 1 Constraint: x 2 – x 1 ≥ d 1 + λ Bellman-Ford minimizes max i {x i } – min i {x i }, which compacts the layout in the x-dimension.