6 006 Introduction to Algorithms Lecture 17 Prof Patrick Jaillet Lecture overview Shortest paths IV 0 3 10 b f 7 3 a b 5 5 a c 8 7 d d 5 a 14 i e 4 g 9 d j 17 h 1 4 review and analysis of Djikstra speeding it up faster special cases implementation one source one target bidirectional goal directed searches 2 1 6 2 5 15 e h 5 8 9th iteration 6 6 i 13 g Dijkstra s algorithm d s 0 for each v V s do d v initialization S Q V while Q do u EXTRACT MIN Q S S u for each v Adj u relaxation do if d v d u w u v then d v d u w u v steps Implicit DECREASE KEY Correctness main argument Theorem Dijkstra s algorithm terminates with d v s v for all v V Proof It suffices to show that d v s v for every v V when v is added to S Suppose u is the first vertex added to S for which d u s u Let y be the first vertex in V S along a shortest path from s to u and let x be its predecessor S just before adding u s u x y Analysis of Dijkstra n times while Q do u EXTRACT MIN Q S S u for each v Adj u do if d v d u w u v degree u then d v d u w u v times DECREASE KEY Time n TEXTRACT MIN m TDECREASE KEY Analysis of Dijkstra continued Time n TEXTRACT MIN m TDECREASE KEY Q array TEXTRACT MIN TDECREASE KEY O n binary O lg n heap Fibonacci O lg n heap amortized Total O 1 O n2 O lg n O m lg n O 1 O n lg n m amortized worst case not covered in 6 006 Special cases of edge weights if edge weights are integral and bounded by a small constant C use an array of lists nC 1 buckets for implementing the priority queue Q TEXTRACT MIN and TDECREASE KEY take O 1 Time Total is then O n m Single source s Single target t S P P d s 0 for each v V s do d v initialization S Q V stop whenever u t while Q do u EXTRACT MIN Q S S u for each v Adj u relaxation do if d v d u w u v then d v d u w u v steps Bi directional Search t S backward search forward search Bi directional Djikstra Alternate forward search from s backward search from t follow edges backward df u distances for forward search db u distances for backward s 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 t 5 5 w Bi directional Dijkstra example u Forward 3 u 3 3 df u 3 s df s 0 Forward 3 s u db u 3 3 s 5 5 w df u 6 df u 3 u t db t 0 5 w db w 5 df w 5 3 u 3 3 t 5 u Backward Backward 3 3 s u db u 3 3 db u 6 u 3 t 5 df s 0 5 5 w t db t 0 5 w db w 5 df w 5 Bi directional Dijkstra example Forward 3 s df s 0 df u 6 u 3 s u 3 t 5 u Backward 3 df u 3 s df u 3 u 5 Backward 3 3 t s u db t 0 5 db w 5 w df u 6 3 db u 6 df w 5 3 u 3 t 5 w Forward u 3 db u 3 3 df u 3 db u 6 u db u 3 df u 6 3 t df s 0 5 5 5 w df w 5 db t 0 5 db w 5 w Bi directional Dijkstra example Forward u 3 u 3 3 df u 3 s df s 0 df u 6 3 t 5 5 w df w 5 df t 10 u Backward s df s 0 db s 10 u 3 3 df u 3 db u 6 5 db u 3 df u 6 t 5 w db w 5 df w 5 deleted from both queues so terminate db t 0 df t 10 Goal directed search or A Idea use a potential function t u over vertices to make the target vertex t more attractive v v increase go uphill 5 5 decrease go downhill Implementation Modify edge weights as follow w u v w u v t u t v Goal directed search or A cont Modify edge weights with potential function over vertices w u v w u v t u t v for any path p between s and t we have w p w p t s t t a path from s to t is a shortest path under w iff it is a shortest path under w Feasible potential and example Potential t u is feasible if w u v w u v t u t v 0 As a result can use Dijkstra with w Examples Euclidean plane Landmarks
View Full Document
Unlocking...