MIT OpenCourseWare http://ocw.mit.edu6.006 Introduction 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 2008 Lecture 18: Shortest Paths IV - Speeding up Dijkstra Lecture 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 BCADE51911715413A 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 1Lecture 18 Shortest Paths III: Dijkstra 6.006 Spring 2008 Bi-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 2Lecture 18 Shortest Paths III: Dijkstra 6.006 Spring 2008 Subtlety: After search terminates, find node x with minimum value of df (x) + db(x). x may not 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 2008 df (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 2008 Feasibility 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
View Full Document
Unlocking...