6.006 16. Shortest paths II: Bellman-Ford Algorithm

MIT OpenCourseWare http://ocw.mit.edu6.006Introduction to AlgorithmsSpring 2008For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. � Lecture 15 Shortest Paths I: Intro 6.006 Spring 2008Lecture 15: Shortest Paths I: Intro Lecture Overview Homework Preview • • 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(VE) is a general algorithm Problem Set 5 Preview: • Use Dijkstra to find shortest path from CalTech to MIT – See “CalTech Cannon Hack” photos (searchweb.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 = (vi,vi+1) �E for 0 ≤ id[u]+ w(u, v): “Relax” edge (u, v) ⎣⎢ d[v] ← d[u]+ w(u, v) π[v] u← until all edges have d[v] ≤ d[u]+ w(u, v) 4Lecture 15 Shortest Paths I: Intro 6.006 Spring 2008Complexity: Termination? (needs to be shown even without negative cycles) Could be exponential time with poor choice of edges. v0v1v2v3v4v5v6v74810121314131011126784689107911T(0) = 0 v0, v1 v1, v2T(n+2) = 3 + 2T(n) v2, vn v0, v2T(n) = (2n/2) v2, vnFigure 3: Running Generic Algorithm Optimal Substructure: Theorem: Subpaths of shortest paths are shortest paths Let p = be a shortest path Let pij = 0 ≤ i ≤ j ≤ k Then pij is a shortest path. Proof: p = v0vivjvkp0jpijpjkpij’Figure 4: Optimal Substructure Theorem If p�ij is shorter than pij , cut out pij and replace with p�ij ; result is shorter than p. Contradiction. 5 Lecture 15 Shortest Paths I: Intro 6.006 Spring 2008Triangle Inequality: Theorem: For all u,v,x �X, we have δ (u, v) ≤ δ (u, x)+ δ (x, v) Proof: uvx(u,v)(x,v)(u,x)Figure 5: Triangle inequality 6