6.006 18.Shortest Paths IV - Speeding up Dijkstra

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 18 Shortest Paths III: Dijkstra 6.006 Spring 2008Lecture 18: Shortest Paths IV -Speeding upDijkstraLecture Overview • Single-source single-target Dijkstra Bidirectional search • • Goal directed search -potentials and landmarks Readings Wagner, Dorothea, and Thomas Willhalm. "Speed-Up Techniques for Shortest-Path Computations." In Lecture Notes in Computer Science: Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science. Berlin/Heidelberg, MA: Springer, 2007. ISBN: 9783540709176. Read up to section 3.2. DIJKSTRA single-source, single-target Initialize() Q V [G] ← while Q = φ do u EXTRACT MIN(Q) (stop if u = t!) ← for each vertex v � Adj[u] do RELAX(u, v, w) Observation: If only shortest path from s to t is required, stop when t is removed from Q, i.e., when u = t DIJKSTRA Demo BC A DE 5 19 11 7 15 4 13 A C E B D 7 12 18 22 D B E C A 4 13 15 22 E C A D B 5 12 13 16 Figure 1: Dijkstra Demonstration with Balls and String 1 Lecture 18 Shortest Paths III: Dijkstra 6.006 Spring 2008Bi-Directional Search Note: Speedup techniques covered here do not change worst-case behavior, but reduce the number of visited vertices in practice. Stforward searchbackward searchFigure 2: Bi-directional SearchBi-D Search Alternate forward search from s backward search from t (follow edges backward) df (u) distances for forward search db(u) distances for backward search Algorithm terminates when some vertex w has been processed, i.e., deleted from the queue of both searches, Qf and Qb s3uu’t3355wFigure 3: Bi-D Search 2 Lecture 18 Shortest Paths III: Dijkstra 6.006 Spring 2008Subtlety: After search terminates, find node x with minimum value of df (x)+ db(x). x maynot be the vertex w that caused termination as in example to the left!Find shortest path from s to x using Πf and shortest path backwards from t to x using Πb.Note: x will have been deleted from either Qf or Qb or both.3u3355df (s) = 0df (u) = 3df (w) = 5Forward33355db(t) = 0db(u’) = 3db (w) = 5Backward33355df (s) = 0df (u’) = 6df (t) = 10Forward33355db(t) = 0db(u) = 6db (w) = 5Backwarddf (u) = 3df (w) = 5df (s) = 0db (s) = 10df (w) = 5df (u) = 3db(u’) = 3df (u’) = 6df (t) = 10uuuu’u’u’u’sssswwwwtttt33355df (s) = 0df (u’) = 6Forward33355db(t) = 0db(u) = 6db (w) = 5Backwarddf (u) = 3df (w) = 5db(u’) = 3uuu’u’sswwttdeleted from both queues so terminate!Figure 4: Forward and Backward Minimum value for df (x)+ db(x) over all vertices that have been processed in at least one search df (u)+ db(u)=3+6=9 3 SearchLecture 18 Shortest Paths III: Dijkstra 6.006 Spring 2008df (u�)+ db(u�)=6+3=9 df (w)+ db(w) = 5+5 = 10 Goal-Directed Search or A∗ Modify edge weights with potential function over vertices. w (u, v)= w (u, v) − λ(u)+ λ(v) Search toward target: vv’55increasego uphilldecreasego downhillFigure 5: Targeted Search Correctness w(p)= w(p) − λt(s)+ λt(t) So shortest paths are maintained in modified graph with w weights. pp’stFigure 6: Modifying Edge Weights To apply Dijkstra, we need w(u, v) ≥ 0 for all (u, v).Choose potential function appropriately, to be feasible.Landmarks Small set of landmarks LCV . For all u�V, l�L, pre-compute δ(u, l).δ(u, l)= δ(t, l) for each l.CLAIM: λt (l) is feasible.Potential λt (l)(u)= 4Lecture 18 Shortest Paths III: Dijkstra 6.006 Spring 2008Feasibility w(u, v) λt(u) = = = = w(u, v) − λ(l) t (u) + λ(l) t (v) w(u, v) − δ(u, l) + δ(t, l) + δ(v, l) − δ(t, l) w(u, v) − δ(u, l) + δ(v, l) ≥ 0 by the Δ -inequality max l � L λ(l) t (u) is also feasible 5