Contents 1 Running Time of Dijkstra 1 2 Bounded Integer Edge Weights 1 3 Single source Single Target SPP 2 1 3 1 Early Termination 2 3 2 Bi directional Search 2 3 3 Potentials 4 Running Time of Dijkstra General Running Time Initialization O V Main loop Every vertex requires exactly one Extract Max we can skip the Inserts if we assume we insert all vertices when they have equal keys of and therefore can insert them in any order Each edge can require up to one Decrease Key and it is possible to come up with a case in which every edge does require a Decrease Key Therefore in terms of these operations the running time is O V TExtract Min O E TDecrease Key We would like Extract Min and Decrease Key to all be constant time but as long as TDecrease Key o V and TExtract Min o E this is still probably better than Bellman Ford Data Structures Structure array binary heap Fibonnacci heap Fibonnaci Heaps Are not part of 6 006 Chapter 20 of CLRS talks about them if you are interested 2 Extract Min O V O log V O log V amortized Decrease Key O 1 O log V O 1 amortized Running Time O V 2 O E log V O V log V E Bounded Integer Edge Weights Assume edge weights are non negative integers bounded by C Use an array of length V C 1 for priority queue where vertices with paths of length i are stored in bucket i Why does this work Because all paths are less than V 1 C V C C 1 V C 1 possible path values When you assign a path length to a previously unassigned node you put it in its correct bucket lives in V C Algorithms Decrease Key v k just moves vertex v from bucket key v to bucket k 1 Extract Max 1 global curr bucket Initialize to zero at start of whole algorithm 2 while curr bucket is empty 3 curr bucket curr bucket 1 4 return First value in curr bucket Correctness of Extract Max By induction Do it yourself Running Time of Decrease Key and Extract Min Clearly Decrease Key is O 1 In addition Extract Max amortizes to O 1 over the course of the whole algorithm we see every bucket once So over the algorithm the time of all calls to Extract Max sums to O V C We extract each vertex once and only once so we make V calls to Extract Max Therefore each call amortizes to O V C O V O 1 Running Time O V E It s linear Circular Queues You can use an array of only length C rather than length V C 1 where path length i is stored in bucket i mod C The correctness of this relies on the fact that the first vertex with path length kC i is not inserted into the queue until we have extracted the last vertex with path length k 1 C i Just argue that since every edge weight is less than C you cannot relax an edge with weight less than k 1 C i and get an edge with weight kC i Do it formally yourself 3 Single source Single Target SPP If you have a negative weight and cycles you can t do better than Bellman Ford since you never know where a negative weight cycle might be lurking You can t stop at t when you reach it So assume non negative weights 3 1 Early Termination We could stop Dijkstra when we hit t In the worst case this is no better but it can help 3 2 Bi directional Search Search from s and t and t to s and hope you meet in the middle Alternate foward from s with backwards from t df is forward distances db is backwards distance Termination Vertex w has been popped o queue in both forwards and backwards search BUT s t df w db w Rather s t minu V df u db u Lemma A s t minu V df u db u 2 Proof Let a shortest path from s to t be u1 u2 u2 u2 un 1 un where u1 s and un t For all shortest paths we must have at least one edge weight wrong min df u db u min s u u t u V u V by the upper bound theorem min s u u t s t u V by the triangle inequality Lemma B Let v be the vertex that has been popped o the queue in both the forward and backwards searches Let p u1 u2 un 1 un be a shortest path from s to t u1 s and un t Let uf be the vertex on this path with the largest df value that has come out of the forward queue and let ub be the vertex on this path with the largest db value that has come out of the backwards queue Then either uf ub or uf ub 1 Proof By the properties of Dijkstra we must have that df uf s uf and db ub ub t Moreover since uf is the largest vertex to have come out of the forwards queue and ub is the largest vertex to come out of the backwards queue and p is a shortest path the following must hold s uf s v 1 ub t v t 3 s uf w uf uf 1 s v w ub 1 ub ub t v t s uf ub t b 1 i f w ui ui 1 s v v t 2 4 5 Combining equations 2 and 4 s uf ub t w uf uf 1 w ub 1 ub s v v t In order that equation 5 hold therefore b 1 i f w ui ui 1 w uf uf 1 w ub 1 ub and we must have either uf ub or uf ub 1 Correctness When a vertex has been popped o the queue of both the forwards and the backwards search s t minu V df u db u Proof We show that there is some vertex q such that s t df q db q The correctness then follows from Lemma A Let p u1 u2 un 1 un be a shortest path from s to t Let uf be the vertex on this path with the largest df that has been popped o the forward queue and let ub be vertex on this path with the largest db that has been popped o the queue Then by the proof of Dijkstra s algorithm we have relaxed u1 u2 uf 1 uf uf uf 1 in order we did the last relaxation when we pushed uf onto the queue Similarly we have relaxed un un 1 ub ub 1 in order in the backwards search By Lemma B 3 uf ub or uf ub 1 In the first case consider vertex uf We have by the path relaxation property that df …
View Full Document
Unlocking...