6.006 Introduction to Algorithms, Lecture 11: Weighted Shortest Paths

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 11: Weighted Shortest Paths Lecture 11: Weighted Shortest Paths Review • Single-Source Shortest Paths with BFS in O(|V | + |E|) time (return distance per vertex) • Single-Source Reachability with BFS or DFS in O(|E|) time (return only reachable vertices) • Connected components with Full-BFS or Full-DFS in O(|V | + |E|) time • Topological Sort of a DAG with Full-DFS in O(|V | + |E|) time • Previously: distance = number of edges in path Today: generalize meaning of distance Weighted Graphs • A weighted graph is a graph G = (V, E) together with a weight function w : E → Z • i.e., assigns each edge e = (u, v) ∈ E an integer weight: w(e) = w(u, v) • Many applications for edge weights in a graph: – distances in road network – latency in network connections – strength of a relationship in a social network • Two common ways to represent weights computationally: – Inside graph representation: store edge weight with each vertex in adjacency lists – Store separate Set data structure mapping each edge to its weight • We assume a representation that allows querying the weight of an edge in O(1) time Examples G1 a −5 6 7 e b −1 −4 3 G2 c 1 8 f g 2 5 a d 9 −2 4 h −5 6 7 e b −1 −4 3 1 8 f g 2 5 c d 9 −2 4 h 2 Lecture 11: Weighted Shortest Paths Weighted Paths • The weight w(π) of a path π in a weighted graph is the sum of weights of edges in the path • The (weighted) shortest path from s ∈ V to t ∈ V is path of minimum weight from s to t • δ(s, t) = inf{w(π) | path π from s to t} is the shortest-path weight from s to t • (Often use “distance” for shortest-path weight in weighted graphs, not number of edges) • As with unweighted graphs: – δ(s, t) = ∞ if no path from s to t – Subpaths of shortest paths are shortest paths (or else could splice in a shorter path) • Why infimum not minimum? Possible that no finite-length minimum-weight path exists • When? Can occur if there is a negative-weight cycle in the graph, Ex: (b, f, g, c, b) in G1 • A negative-weight cycle is a path π starting and ending at same vertex with w(π) < 0 • δ(s, t) = −∞ if there is a path from s to t through a vertex on a negative-weight cycle • If this occurs, don’t want a shortest path, but may want the negative-weight cycle Weighted Shortest Paths Algorithms • Next four lectures: algorithms to find shortest-path weights in weighted graphs • (No parent pointers: can reconstruct shortest paths tree in linear time after. Next page!) • Already know one algorithm: Breadth-First Search! Runs in O(|V | + |E|) time when, e.g.: – graph has positive weights, and all weights are the same – graph has positive weights, and sum of all weights at most O(|V | + |E|) • For general weighted graphs, we don’t know how to solve SSSP in O(|V | + |E|) time • But if your graph is a Directed Acyclic Graph you can! 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 (Today!) L12 L13 Lecture 11: Weighted Shortest Paths 3 Shortest-Paths Tree • For BFS, we kept track of parent pointers during search. Alternatively, compute them after! • If know δ(s, v) for all vertices v ∈ V , can construct shortest-path tree in O(|V | + |E|) time • For weighted shortest paths from s, only need parent pointers for vertices v with finite δ(s, v) • Initialize empty P and set P (s) = None • For each vertex u ∈ V where δ(s, v) is finite: – For each outgoing neighbor v ∈ Adj+ (u): ∗ If P (v) not assigned and δ(s, v) = δ(s, u) + w(u, v): · There exists a shortest path through edge (u, v), so set P (v) = u • Parent pointers may traverse cycles of zero weight. Mark each vertex in such a cycle. • For each unmarked vertex u ∈ V (including vertices later unmarked): – For each v ∈ Adj+ (u) where v is marked and δ(s, v) = δ(s, u) + w(u, v): ∗ Unmark vertices in cycle containing v by traversing parent pointers from v ∗ Set P (v) = u, breaking the cycle • Exercise: Prove this algorithm correctly computes parent pointers in linear time • Because we can compute parent pointers afterward, we focus on computing distances DAG Relaxation • Idea! Maintain a distance estimate d(s, v) (initially ∞) for each vertex v ∈ V , that always upper bounds true distance δ(s, v), then gradually lowers until d(s, v) = δ(s, v) • When do we lower? When an edge violates the triangle inequality! • Triangle Inequality: the shortest-path weight from u to v cannot be greater than the shortest path from u to v through another vertex x, i.e., δ(u, v) ≤ δ(u, x) + δ(x, v) for all u, v, x ∈ V • If d(s, v) > d(s, u) + w(u, v) for some edge (u, v), then triangle inequality is violated :( • Fix by lowering d(s, v) to d(s, u) + w(u, v), i.e., relax (u, v) to satisfy violated constraint • Claim: Relaxation is safe: maintains that each d(s, v) is weight of a path to v (or ∞) ∀v ∈ V • Proof: Assume d(s, v 0 ) is weight of a path (or ∞) for all v 0 ∈ V . Relaxing some edge (u, v) sets d(s, v) to d(s, u) + w(u, v), which is the weight of a path from s to v through u. 4 Lecture 11: Weighted Shortest Paths • Set d(s, v) = ∞ for all v ∈ V , then set d(s, s) = 0 • Process each vertex u in a topological sort order of G: – For each outgoing neighbor v ∈ Adj+ (u): ∗ If d(s, v) > d(s, u) + w(u, v): · relax edge (u, v), i.e., set d(s, v) = d(s, u) + w(u, v) • Example: Run DAG Relaxation from vertex a in G2 Correctness • Claim: At end of DAG Relaxation: d(s, v) = δ(s, v) for all v ∈ V • Proof: Induct on k: d(s, v) = δ(s, v) for all v in first k vertices in topological order – Base case: Vertex s and every vertex before s in topological order satisfies claim at start – Inductive step: Assume claim holds for first k 0 vertices, let v be the (k 0 + 1)th – Consider a shortest path from s to v, and let u be the vertex preceding v on path – u occurs before v in topological order, so d(s, u) = δ(s, u) by induction – When processing u, d(s, v) is set to be no larger (≤) than δ(s, u) + w(u, v) = δ(s, v) – But d(s, v) ≥ δ(s, v), since relaxation is safe, so d(s, v) = δ(s, v) • Alternatively: – For any vertex v, DAG relaxation sets d(s, v) = min{d(s, u) + w(u, v) | u ∈ Adj− (v)} – Shortest path to v must pass through some incoming neighbor u of v – So if d(s, u) = δ(s, u) for all u ∈ Adj− (v) by induction, then d(s, v) = δ(s, v) Running Time • Initialization takes O(|V |) time, and Topological Sort takes O(|V | + |E|) time P • Additional work upper bounded by O(1) × u∈V deg+ (u) = O(|E|) • Total running time is linear, O(|V | + |E|)