6.006 Introduction to Algorithms, Lecture 12: Bellman-Ford

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 12: Bellman-Ford Lecture 12: Bellman-Ford Previously • Weighted graphs, shortest-path weight, negative-weight cycles • Finding shortest-path tree from shortest-path weights in O(|V | + |E|) time • DAG Relaxation: algorithm to solve SSSP on a weighted DAG in O(|V | + |E|) time • SSSP for graph with negative weights – Compute δ(s, v) for all v ∈ V (−∞ if v reachable via negative-weight cycle) – If a negative-weight cycle reachable from s, return one Warmups • Exercise 1: Given undirected graph G, return whether G contains a negative-weight cycle • Solution: Return Yes if there is an edge with negative weight in G in O(|E|) time :O • So for this lecture, we restrict our discussion to directed graphs • Exercise 2: Given SSSP algorithm A that runs in O(|V |(|V | + |E|) time, show how to use it to solve SSSP in O(|V ||E|) time • Solution: Run BFS or DFS to find the vertices reachable from s in O(|E|) time – Mark each vertex v not reachable from s with δ(s, v) = ∞ in O(|V |) time – Make graph G0 = (V 0 , E 0 ) with only vertices reachable from s in O(|V | + |E|) time – Run A from s in G0 . – G0 is connected, so |V 0 | = O(|E 0 |) = O(|E|) so A runs in O(|V ||E|) time • Today, we will find a SSSP algorithm with this running time that works for general graphs! Restrictions Graph Weights Name General DAG General General BFS DAG Relaxation Bellman-Ford Dijkstra Unweighted Any Any Non-negative SSSP Algorithm Running Time O(·) |V | + |E| |V | + |E| |V | · |E| |V | log |V | + |E| Lecture L09 L11 L12 (Today!) L13 2 Lecture 12: Bellman-Ford Simple Shortest Paths • If graph contains cycles and negative weights, might contain negative-weight cycles :( • If graph does not contain negative-weight cycles, shortest paths are simple! • Claim 1: If δ(s, v) is finite, there exists a shortest path to v that is simple • Proof: By contradiction: – Suppose no simple shortest path; let π be a shortest path with fewest vertices – π not simple, so exists cycle C in π; C has non-negative weight (or else δ(s, v) = −∞) – Removing C from π forms path π 0 with fewer vertices and weight w(π 0 ) ≤ w(π) • Since simple paths cannot repeat vertices, finite shortest paths contain at most |V | − 1 edges Negative Cycle Witness • k-Edge Distance δk (s, v): the minimum weight of any path from s to v using ≤ k edges • Idea! Compute δ|V |−1 (s, v) and δ|V | (s, v) for all v ∈ V – If δ(s, v) = 6 −∞, δ(s, v) = δ|V |−1 (s, v), since a shortest path is simple (or nonexistent) – If δ|V | (s, v) < δ|V |−1 (s, v) ∗ there exists a shorter non-simple path to v, so δ|V | (s, v) = −∞ ∗ call v a (negative cycle) witness – However, there may be vertices with −∞ shortest-path weight that are not witnesses • Claim 2: If δ(s, v) = −∞, then v is reachable from a witness • Proof: Suffices to prove: every negative-weight cycle reachable from s contains a witness – Consider a negative-weight cycle C reachable from s – For v ∈ C, let v 0 ∈ C denote v’s predecessor in C, where P v∈C w(v 0 , v) < 0 – Then δ|V | (s, v) ≤ δ|V |−1 (s, v 0 )+w(v 0 , v) (RHS weight of some path on ≤ |V | vertices) P P P P δ|V |−1 (s, v 0 ) + w(v 0 , v) < δ|V |−1 (s, v) – So δ|V | (s, v) ≤ v∈C v∈C v∈C v∈C – If C contains no witness, δ|V | (s, v) ≥ δ|V |−1 (s, v) for all v ∈ C, a contradiction Lecture 12: Bellman-Ford 3 Bellman-Ford • Idea! Use graph duplication: make multiple copies (or levels) of the graph • |V | + 1 levels: vertex vk in level k represents reaching vertex v from s using ≤ k edges • If edges only increase in level, resulting graph is a DAG! • Construct new DAG G0 = (V 0 , E 0 ) from G = (V, E): – G0 has |V |(|V | + 1) vertices vk for all v ∈ V and k ∈ {0, . . . , |V |} – G0 has |V |(|V | + |E|) edges: ∗ |V | edges (vk−1 , vk ) for k ∈ {1, . . . , |V |} of weight zero for each v ∈ V ∗ |V | edges (uk−1 , vk ) for k ∈ {1, . . . , |V |} of weight w(u, v) for each (u, v) ∈ E • Run DAG Relaxation on G0 from s0 to compute δ(s0 , vk ) for all vk ∈ V 0 • For each vertex: set d(s, v) = δ(s0 , v|V |−1 ) • For each witness u ∈ V where δ(s0 , u|V | ) < δ(s0 , u|V |−1 ): – For each vertex v reachable from u in G: ∗ set d(s, v) = −∞ Example G G0 −5 a 6 a0 b −1 −4 0 c d 3 b0 −5 c0 6 −4 0 0 d0 −1 3 0 a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3 a4 b4 c4 d4 δ(a0 , vk ) k\v a b c d 0 1 2 3 4 0 0 0 0 0 ∞ −5 −5 −5 −7 ∞ 6 −9 −9 −9 ∞ ∞ 9 −6 −6 δ(a, v) 0 −∞ −∞ −∞ 4 Lecture 12: Bellman-Ford Correctness • Claim 3: δ(s0 , vk ) = δk (s, v) for all v ∈ V and k ∈ {0, . . . , |V |} • Proof: By induction on k: – Base case: true for all v ∈ V when k = 0 (only v0 reachable from s0 is v = s) – Inductive Step: Assume true for all k < k 0 , prove for k = k 0 δ(s0 , vk0 ) = min{δ(s0 , uk0 −1 ) + w(uk0 −1 , vk0 ) | uk0 −1 ∈ Adj− (vk0 )} = min{{δ(s0 , uk0 −1 ) + w(u, v) | u ∈ Adj− (v)} ∪ {δ(s0 , vk0 −1 )}} = min{{δk0 −1 (s, u) + w(u, v) | u ∈ Adj− (v)} ∪ {δk0 −1 (s, v)}} (by induction) = δk0 (s, v) • Claim 4: At the end of Bellman-Ford d(s, v) = δ(s, v) • Proof: Correctly computes δ|V |−1 (s, v) and δ|V | (s, v) for all v ∈ V by Claim 3 – If δ(s, v) = 6 −∞, correctly sets d(s, v) = δ|V |−1 (s, v) = δ(s, v) – Then sets d(s, v) = −∞ for any v reachable from a witness; correct by Claim 2 Running Time • G0 has size O(|V |(|V | + |E|)) and can be constructed in as much time • Running DAG Relaxation on G0 takes linear time in the size of G0 • Does O(1) work for each vertex reachable from a witness • Finding reachability of a witness takes O(|E|) time, with at most O(|V |) witnesses: O(|V ||E|) • (Alternatively, connect super node x to witnesses via 0-weight edges, linear search from x) • Pruning G at start to only subgraph reachable from s yields O(|V ||E|)-time algorithm Extras: Return Negative-Weight Cycle or Space Optimization • Claim 5: Shortest s0 − v|V | path π for any witness v contains a negative-weight cycle in G • Proof: Since π contains |V | + 1 vertices, must contain at least one cycle C in G – C has negative weight (otherwise, remove C to make path π 0 with fewer vertices and w(π 0 ) ≤ w(π), contradicting witness v) • Can use just O(|V |) space by storing only δ(s0 , vk−1 ) and δ(s0 , vk ) for each k from 1 to |V | • Traditionally, Bellman-Ford stores only one value per vertex, attempting to relax every edge in |V | rounds; but estimates do not correspond to k-Edge Distances, so analysis trickier • But these space optimizations don’t return a negative weight cycle