Lecture 15 Shortest Paths I: Intro 6.006 Fall 2011 Lecture 15: Shortest Paths I: Intro Lecture Overview • Weighted Graphs • General Approach • Negative Edges • Optimal Substructure Readings CLRS, Sections 24 (Intro) Motivation: Shortest way to drive from A to B Google maps “get directions” Formulation: Problem on a weighted graph G(V, E) W : E → < Two algorithms: Dijkstra O(V lg V + E) assumes non-negative edge weights Bellman Ford O(V E) is a general algorithm Application • Find shortest path from CalTech to MIT – See “CalTech Cannon Hack” photos web.mit.edu – See Google Maps from CalTech to MIT • Model as a weighted graph G(V, E), W : E → < – V = vertices (street intersections) – E = edges (street, roads); directed edges (one way roads) – W (U, V ) = weight of edge from u to v (distance, toll) path p = < v0 , v1 , . . . vk > (vi , vi+1 ) ∈ E for 0 ≤ i < k k−1 X w(p) = w(vi , vi+1 ) i=0 1 Lecture 15 Shortest Paths I: Intro 6.006 Fall 2011 Weighted Graphs: Notation: p means p is a path from v0 to vk . (v0 ) is a path from v0 to v0 of weight v0 −→ vk 0. Definition: Shortest path weight from u to v as  p  min w(p) : if ∃ any such path δ(u, v) = u −→ v  ∞ otherwise (v unreachable from u) Single Source Shortest Paths: Given G = (V, E), w and a source vertex S, find δ(S, V ) [and the best path] from S to each v ∈ V . Data structures: d[v] = value inside circle 0 if v = s = ⇐= ∞ otherwise = δ (s, v) ⇐= at end d[v] ≥ δ(s, v) at all times d[v] decreases as we find better paths to v, see Figure 1. Π[v] = predecessor on best path to v, Π[s] = NIL 2 initially Lecture 15 Shortest Paths I: Intro 6.006 Fall 2011 Example: 2 A 1 1 S 2 2 E 3 5 3 3 1 0 C 5 3 2 1 3 D B 1 1 4 4 F 2 Figure 1: Shortest Path Example: Bold edges give predecessor Π relationships Negative-Weight Edges: • Natural in some applications (e.g., logarithms used for weights) • Some algorithms disallow negative weight edges (e.g., Dijkstra) • If you have negative weight edges, you might also have negative weight cycles =⇒ may make certain shortest paths undefined! Example: See Figure 2 B → D → C → B (origin) has weight −6 + 2 + 3 = −1 < 0! Shortest path S −→ C (or B, D, E) is undefined. Can go around B → D → C as 3 Lecture 15 Shortest Paths I: Intro 6.006 Fall 2011 C 4 S 2 B -2 3 E 2 -6 A 1 D Figure 2: Negative-weight Edges. many times as you like Shortest path S −→ A is defined and has weight 2 If negative weight edges are present, s.p. algorithm should find negative weight cycles (e.g., Bellman Ford) General structure of S.P. Algorithms (no negative cycles) Initialize: Main: “Relax” edge (u, v) for v ∈ V : d [v] Π [v] ← ← ∞ NIL d[S] ← 0 repeat select edge (u, v) [somehow]  if d[v] > d[u] + w(u, v) :  d[v] ← d[u] + w(u, v) π[v] ← u until all edges have d[v] ≤ d[u] + w(u, v) 4 Lecture 15 Shortest Paths I: Intro 6.006 Fall 2011 Complexity: Termination? (needs to be shown even without negative cycles) Could be exponential time with poor choice of edges. v0 v1 v2 v3 v4 v5 v6 4 8 10 12 13 14 13 12 11 10 9 8 7 T(n+2) = 3 + 2T(n) v0, v1 v1, v2 v2, vn T(n) = θ(2 ) v0, v2 v2, vn T(0) = 0 n/2 4 6 10 11 8 9 6 7 v7 Figure 3: Running Generic Algorithm. The outgoing edges from v0 and v1 have weight 4, the outgoing edges from v2 and v3 have weight 2, the outgoing edges from v4 and v5 have weight 1. In a generalized example based on Figure 3, we have n nodes, and the weights of n n edges in the first 3-tuple of nodes are 2 2 . The weights on the second set are 2 2 −1 , and so on. A pathological selection of edges will result in the initial value of d(vn−1 ) n n to be 2 × (2 2 + 2 2 −1 + · · · + 4 + 2 + 1). In this ordering, we may then relax the edge of weight 1 that connects vn−3 to vn−1 . This will reduce d(vn−1 ) by 1. After we relax the edge between vn−5 and vn−3 of weight 2, d(vn−2 ) reduces by 2. We then might relax the edges (vn−3 , vn−2 ) and (vn−2 , vn−1 ) to reduce d(vn−1 ) by 1. Then, we relax the edge from vn−3 to vn−1 again. In this manner, we might reduce d(vn−1 ) by 1 at n n n each relaxation all the way down to 2 2 + 2 2 −1 + · · · + 4 + 2 + 1. This will take O(2 2 ) time. Optimal Substructure: Theorem: Subpaths of shortest paths are shortest paths Let p = < v0 , v1 , . . . vk > be a shortest path Let pij = < vi , vi+1 , . . . vj > 0 ≤ i ≤ j ≤ k 5 Lecture 15 Shortest Paths I: Intro 6.006 Fall 2011 Then pij is a shortest path. p0,i pij pjk v → vi → vj → vk Proof: p = 0 → p0ij 0 If pij is shorter than pij , cut out pij and replace with p0ij ; result is shorter than p. Contradiction. Triangle Inequality: Theorem: For all u, v, x ∈ X, we have δ (u, v) ≤ δ (u, x) + δ (x, v) Proof: δ (u,v) v u δ (x,v) δ (u,x) x Figure 4: Triangle inequality 6