6.006 Introduction to Algorithms, Lecture 14: Johnson's Algorithm

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 14: Johnson’s Algorithm Lecture 14: Johnson’s Algorithm Previously Restrictions Graph Weights General Unweighted DAG Any General Non-negative General Any SSSP Algorithm Name Running Time O(·) BFS |V | + |E| DAG Relaxation |V | + |E| Dijkstra |V | log |V | + |E| Bellman-Ford |V | · |E| All-Pairs Shortest Paths (APSP) • Input: directed graph G = (V, E) with weights w : E → Z • Output: δ(u, v) for all u, v ∈ V , or abort if G contains negative-weight cycle • Useful when understanding whole network, e.g., transportation, circuit layout, supply chains... • Just doing a SSSP algorithm |V | times is actually pretty good, since output has size O(|V |2 ) – |V | · O(|V | + |E|) with BFS if weights positive and bounded by O(|V | + |E|) – |V | · O(|V | + |E|) with DAG Relaxation if acyclic – |V | · O(|V | log |V | + |E|) with Dijkstra if weights non-negative or graph undirected – |V | · O(|V | · |E|) with Bellman-Ford (general) • Today: Solve APSP in any weighted graph in |V | · O(|V | log |V | + |E|) time 2 Lecture 14: Johnson’s Algorithm Approach • Idea: Make all edge weights non-negative while preserving shortest paths! • i.e., reweight G to G0 with no negative weights, where a shortest path in G is shortest in G0 • If non-negative, then just run Dijkstra |V | times to solve APSP • Claim: Can compute distances in G from distances in G0 in O(|V |(|V | + |E|)) time – Compute shortest-path tree from distances, for each s ∈ V 0 in O(|V | + |E|) time (L11) – Also shortest-paths tree in G, so traverse tree with DFS while also computing distances – Takes O(|V | · (|V | + |E|)) time (which is less time than |V | times Dijkstra) • But how to make G0 with non-negative edge weights? Is this even possible?? • Claim: Not possible if G contains a negative-weight cycle • Proof: Shortest paths are simple if no negative weights, but not if negative-weight cycle • Given graph G with negative weights but no negative-weight cycles, can we make edge weights non-negative while preserving shortest paths? Making Weights Non-negative • Idea! Add negative of smallest weight in G to every edge! All weights non-negative! • FAIL: Does not preserve shortest paths! Biases toward paths traversing fewer edges :) :( • Idea! Given vertex v, add h to all outgoing edges and subtract h from all incoming edges • Claim: Shortest paths are preserved under the above reweighting • Proof: – Weight of every path starting at v changes by h – Weight of every path ending at v changes by −h – Weight of a path passing through v does not change (locally) • This is a very general and useful trick to transform a graph while preserving shortest paths! Lecture 14: Johnson’s Algorithm 3 • Even works with multiple vertices! • Define a potential function h : V → Z mapping each vertex v ∈ V to a potential h(v) • Make graph G0 : same as G but edge (u, v) ∈ E has weight w0 (u, v) = w(u, v) + h(u) − h(v) • Claim: Shortest paths in G are also shortest paths in G0 • Proof: P – Weight of path π = (v0 , . . . , vk ) in G is w(π) = ki=1 w(vi−1 , vi ) P – Weight of π in G0 is: ki=1 w(vi−1 , vi ) + h(vi−1 ) − h(vi ) = w(π) + h(v0 ) − h(vk ) – (Sum of h’s telescope, since there is a positive and negative h(vi ) for each interior i) – Every path from v0 to vk changes by the same amount – So any shortest path will still be shortest Making Weights Non-negative • Can we find a potential function such that G0 has no negative edge weights? • i.e., is there an h such that w(u, v) + h(u) − h(v) ≥ 0 for every (u, v) ∈ E? • Re-arrange this condition to h(v) ≤ h(u) + w(u, v), looks like triangle inequality! • Idea! Condition would be satisfied if h(v) = δ(s, v) and δ(s, v) is finite for some s • But graph may be disconnected, so may not exist any such vertex s... :( • Idea! Add a new vertex s with a directed 0-weight edge to every v ∈ V ! :) • δ(s, v) ≤ 0 for all v ∈ V , since path exists a path of weight 0 • Claim: If δ(s, v) = −∞ for any v ∈ V , then the original graph has a negative-weight cycle • Proof: – Adding s does not introduce new cycles (s has no incoming edges) – So if reweighted graph has a negative-weight cycle, so does the original graph • Alternatively, if δ(s, v) is finite for all v ∈ V : – w0 (u, v) = w(u, v) + h(u) − h(v) ≥ 0 for every (u, v) ∈ E by triangle inequality! – New weights in G0 are non-negative while preserving shortest paths! 4 Lecture 14: Johnson’s Algorithm Johnson’s Algorithm • Construct Gx from G by adding vertex x connected to each vertex v ∈ V with 0-weight edge • Compute δx (x, v) for every v ∈ V (using Bellman-Ford) • If δx (x, v) = −∞ for any v ∈ V : – Abort (since there is a negative-weight cycle in G) • Else: – Reweight each edge w0 (u, v) = w(u, v) + δx (x, u) − δx (x, v) to form graph G0 – For each u ∈ V : ∗ Compute shortest-path distances δ 0 (u, v) to all v in G0 (using Dijkstra) ∗ Compute δ(u, v) = δ 0 (u, v) − δx (x, u) + δx (x, v) for all v ∈ V Correctness • Already proved that transformation from G to G0 preserves shortest paths • Rest reduces to correctness of Bellman-Ford and Dijkstra • Reducing from Signed APSP to Non-negative APSP • Reductions save time! No induction today! :) Running Time • O(|V | + |E|) time to construct Gx • O(|V ||E|) time for Bellman-Ford • O(|V | + |E|) time to construct G0 • O(|V | · (|V | log |V | + |E|)) time for |V | runs of Dijkstra • O(|V |2 ) time to compute distances in G from distances in G0 • O(|V |2 log |V | + |V ||E|) time in total