MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For 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 4 B 19 15 11 A 13 7 5 C A C E B D 7 12 18 22 D D B E C A 4 13 15 22 E 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 2008 Bi Directional Search Note Speedup techniques covered here do not change worst case behavior but reduce the number of visited vertices in practice t S backward search forward search Figure 2 Bi directional Search Bi 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 u u 3 3 3 s t 5 5 w Figure 3 Bi D Search 2 Lecture 18 Shortest Paths III Dijkstra 6 006 Spring 2008 Subtlety After search terminates nd 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 u Forward 3 df s 0 df u 6 5 w u Backward 3 s t 5 t df t 10 df s 0 db s 10 df w 5 db t 0 5 db w 5 w 3 df u 3 s df s 0 u 3 5 df w 5 3 u 3 db u 6 s 5 u 3 3 t db u 3 u Backward 3 5 t db t 0 5 w db w 5 u 3 w Forward 5 df w 5 df u 3 s s df u 6 u 3 db u 3 3 5 w u 3 3 t 5 df s 0 u Backward 3 df u 3 s Forward u 3 u 3 3 df u 3 db u 6 5 db u 3 df u 6 t 5 w db t 0 df t 10 db w 5 df w 5 deleted from both queues so terminate Figure 4 Forward and Backward Search 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 Lecture 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 v v increase go uphill 5 5 decrease go downhill Figure 5 Targeted Search Correctness w p w p t s t t So shortest paths are maintained in modi ed graph with w weights p s t p Figure 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 l Small set of landmarks LCV For all u V l L pre compute u l Potential t u u l t l for each l l CLAIM t is feasible 4 Lecture 18 Shortest Paths III Dijkstra 6 006 Spring 2008 Feasibility l l w u v w u v t u t v w u v u l t l v l t l w u v u l v l 0 t u l max t u l L is also feasible 5 by the inequality
View Full Document
Unlocking...