麻省理工学院：算法导论（英文）：lecture19

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 19 Prof. Erik Demaine Introduction to Algorithms Day 32 L19.2? 2001 by Charles E. Leiserson Shortest paths Single-source shortest paths ? Nonnegative edge weights ? Dijkstra’s algorithm: O(E + V lg V) ? General ? Bellman-Ford: O(VE) ? DAG ? One pass of Bellman-Ford: O(V + E) All-pairs shortest paths ? Nonnegative edge weights ? Dijkstra’s algorithm |V| times: O(VE + V 2 lg V) ? General ? Three algorithms today. Introduction to Algorithms Day 32 L19.3? 2001 by Charles E. Leiserson All-pairs shortest paths Input: Digraph G = (V, E), where |V| = n, with edge-weight function w : E →R. Output: n × n matrix of shortest-path lengths δ(i, j) for all i, j ∈ V. IDEA #1: ? Run Bellman-Ford once from each vertex. ? Time = O(V 2 E). ? Dense graph ? O(V 4 ) time. Good first try! Introduction to Algorithms Day 32 L19.4? 2001 by Charles E. Leiserson Dynamic programming Consider the n × n adjacency matrix A = (a ij ) of the digraph, and define d ij (0) = 0 if i = j, ∞ if i ≠ j; Claim: We have and for m = 1, 2, …, n –1, d ij (m) = min k {d ik (m–1) + a kj }. d ij (m) = weight of a shortest path from i to j that uses at most m edges. Introduction to Algorithms Day 32 L19.5? 2001 by Charles E. Leiserson Proof of claim d ij (m) = min k {d ik (m–1) + a kj } i i j j M k’s ≤ m – 1 e d g e s ≤ m – 1 e d g e s ≤ m – 1 e d g e s ≤ m –1edges Relaxation! for k ← 1 to n do if d ij > d ik + a kj then d ij ← d ik + a kj Note: No negative-weight cycles implies δ(i, j) = d ij (n–1) = d ij (n) = d ij (n+1) = L Introduction to Algorithms Day 32 L19.6? 2001 by Charles E. Leiserson Matrix multiplication Compute C = A · B, where C, A, and B are n × n matrices: ∑ = = n k kjikij bac 1 . Time = Θ(n 3 ) using the standard algorithm. What if we map “+” → “min” and “·” → “+”? c ij = min k {a ik + b kj }. Thus, D (m) = D (m–1) “×” A. Identity matrix = I = ? ? ? ? ? ? ? ? ? ? ∞∞∞ ∞∞∞ ∞∞∞ ∞∞∞ 0 0 0 0 = D 0 = (d ij (0) ). Introduction to Algorithms Day 32 L19.7? 2001 by Charles E. Leiserson Matrix multiplication (continued) The (min, +) multiplication is associative, and with the real numbers, it forms an algebraic structure called a closed semiring. Consequently, we can compute D (1) = D (0) · A = A 1 D (2) = D (1) · A = A 2 MM D (n–1) = D (n–2) · A = A n–1 , yielding D (n–1) = (δ(i, j)). Time = Θ(n·n 3 ) = Θ(n 4 ). No better than n × B-F. Introduction to Algorithms Day 32 L19.8? 2001 by Charles E. Leiserson Improved matrix multiplication algorithm Repeated squaring: A 2k = A k × A k . Compute A 2 , A 4 , …, A 2 ?lg(n–1)? . O(lg n) squarings Time = Θ(n 3 lg n). To detect negative-weight cycles, check the diagonal for negative values in O(n) additional time. Note: A n–1 = A n = A n+1 = L . Introduction to Algorithms Day 32 L19.9? 2001 by Charles E. Leiserson Floyd-Warshall algorithm Also dynamic programming, but faster! Define c ij (k) = weight of a shortest path from i to j with intermediate vertices belonging to the set {1, 2, …, k}. i i ≤ k ≤ k ≤ k ≤ k ≤ k ≤ k ≤ k ≤ k j j Thus, δ(i, j) = c ij (n) . Also, c ij (0) = a ij . Introduction to Algorithms Day 32 L19.10? 2001 by Charles E. Leiserson Floyd-Warshall recurrence c ij (k) = min k {c ij (k–1) , c ik (k–1) + c kj (k–1) } i i j j k c ij (k–1) c ik (k–1) c kj (k–1) intermediate vertices in {1, 2, …, k} Introduction to Algorithms Day 32 L19.11? 2001 by Charles E. Leiserson Pseudocode for Floyd- Warshall for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do if c ij > c ik + c kj then c ij ← c ik + c kj relaxation Notes: ? Okay to omit superscripts, since extra relaxations can’t hurt. ? Runs in Θ(n 3 ) time. ? Simple to code. ? Efficient in practice. Introduction to Algorithms Day 32 L19.12? 2001 by Charles E. Leiserson Transitive closure of a directed graph Compute t ij = 1 if there exists a path from i to j, 0 otherwise. IDEA: Use Floyd-Warshall, but with (∨, ∧) instead of (min, +): t ij (k) = t ij (k–1) ∨ (t ik (k–1) ∧ t kj (k–1) ). Time = Θ(n 3 ). Introduction to Algorithms Day 32 L19.13? 2001 by Charles E. Leiserson Graph reweighting Theorem. Given a label h(v) for each v ∈ V, reweight each edge (u, v) ∈ E by ?(u, v) = w(u, v) + h(u) – h(v). Then, all paths between the same two vertices are reweighted by the same amount. Proof. Let p = v 1 → v 2 → L → v k be a path in the graph. () )()()( )()(),( )()(),( ),(?)(? 1 1 1 1 1 1 1 11 1 1 1 k k k i ii k i iiii k i ii vhvhpw vhvhvvw vhvhvvw vvwpw ?+= ?+= ?+= = ∑ ∑ ∑ ? = + ? = ++ ? = + . Then, we have Introduction to Algorithms Day 32 L19.14? 2001 by Charles E. Leiserson Johnson’s algorithm 1. Find a vertex labeling h such that ?(u, v) ≥ 0 for all (u, v) ∈ E by using Bellman-Ford to solve the difference constraints h(v) – h(u) ≤ w(u, v), or determine that a negative-weight cycle exists. ? Time = O(VE). 2. Run Dijkstra’s algorithm from each vertex using ?. ? Time = O(VE + V 2 lg V). 3. Reweight each shortest-path length ?(p) to produce the shortest-path lengths w(p) of the original graph. ? Time = O(V 2 ). Total time = O(VE+ V 2 lg V).