6.006 17. Shortest Paths III - Dijkstra and Special Cases

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 17 Shortest Paths III: Dijkstra 6.006 Spring 2008Lecture 17: Shortest Paths III -Dijkstra andSpecial CasesLecture Overview • Shortest paths in DAGs • Shortest paths in graphs without negative edges • Dijkstra’s Algorithm Readings CLRS, Sections 24.2-24.3 DAGs: Can’t have negative cycles because there are no cycles! 1. Topologically sort the DAG. Path from u to v implies that u is before v in the linear ordering 2. One pass over vehicles in topologically sorted order relaxing each edge that leaves each vertex Θ(V + E) time Example: rstxyz03527-1641-22Figure 1: Shortest Path using Topological Sort Vertices sorted left to right in topological order Process r: stays ∞. All vertices to the left of s will be ∞ by definition Process s: t : ∞→ 2 x : ∞→ 6 (see top of Figure 2) 1 � Lecture 17 Shortest Paths III: Dijkstra 6.006 Spring 2008rstxyz0263527-1641-22rstxyz026533527-1641-22process t, x, yFigure 2: Preview of Dynamic Programming Dijkstra’s Algorithm For each edge (u, v) �E, assume w(u, v) ≥ 0, maintain a set S of vertices whose final shortest path weights have been determined. Repeatedly select u�V − S with minimum shortest path estimate, add u to S, relax all edges out of u. Pseudo-code Dijkstra (G, W, s) //uses priority queue Q Initialize (G, s) Sφ← QV [G] //Insert into Q←while Q = φ do u EXTRACT-MIN(Q) //deletes u from Q← S = S ∪{u}for each vertex v� Adj[u] do RELAX (u, v, w) this is an implicit DECREASE KEY operation ← 2 Lecture 17 Shortest Paths III: Dijkstra 6.006 Spring 2008Recall RELAX(u, v, w) if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) TT[v] ← u Example BCA0DE2210138497S = { } { A B C D E } = QS = { A } 0 S = { A, C } 0 10 3 after relaxing edges from AS = { A, C } 0 7 3 11 5 after relaxing edges from C S = { A, C, E } 0 7 3 11 5 S = { A, C , E, B} 0 7 3 9 5 after relaxing edges from B Figure 3: Dijkstra Execution Strategy: Dijkstra is a greedy algorithm: choose closest vertex in V − S to add to set S Correctness: Each time a vertex u is added to set S, we have d[u]= δ(s, u) 3 Lecture 17 Shortest Paths III: Dijkstra 6.006 Spring 2008Complexity θ(v) inserts into priority queue θ(v) EXTRACT MIN operations θ(E) DECREASE KEY operations Array impl: θ(v) time for extra min θ(1) for decrease key Total: θ(V.V + E.1) = θ(V 2 + E)= θ(V 2) Binary min-heap: θ(lg V ) for extract min θ(lg V ) for decrease key Total: θ(V lg V + E lg V ) Fibonacci heap (not covered in 6.006): θ(lg V ) for extract min θ(1) for decrease key amortized cost Total: θ(V lg V + E) 4