Contents1 Running Time of Dijkstra 12 Bounded Integer Edge Weights 13 Single source, Single Target (SPP) 23.1 Early Termination: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23.2 Bi-directional Search: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23.3 Potentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Running Time of Di j ks t raGeneral Running Time: Initialization: O(|V |), Main loop: Every vertex requires exactly oneExtract-Max (we can skip the Inserts if we assume we insert all vertices when they have equalkeys of ∞ and therefore can insert them in any order). Each edge can require up to one Decrease-Keyand it is possible to c ome up with a case in which every edge does require a Decrease-Key. T he re for e,in terms of these op er at i ons the runni n g 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 b et t er than Bellm an- Ford!Data Structures:Structure Extract-Min Decrease-Key Running Timearray O(|V |) O(1) O(|V |2)binary heap O(log |V |) O(log |V |) O(|E| log |V |)Fibonnacci heap O(log |V |) amortized O(1) amortized O(|V | log |V | + |E|)Fibonnaci Heaps: Are not part of 6.006. Chapter 20 of CLRS t al ks about them if you are interested.2 Bounded Integer Edge WeightsAssume edge weights are non-negative integers bounded by C. Use an array of length |V |C + 1 forpriority 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 possiblepath 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)justmovesvertexv from bucket key[v]tobucketk.1Extract-Max1 global curr-bucket // Initialize to zero at start of whole algor i thm2 while (curr-bucket is empty)3 curr-bucket← curr-bucket +14 return First value in curr-bucketCorrectness of Extract-Max: By induction. D o it yourself.Running Time of Decre as e -Ke y and Extract-Min: Clearly Decrease-Ke y is O(1). In ad-dition, Extract-Max amortizes to O(1): over the course of the whole algorithm we see every bucketonce. So, over the algorithm, the time of all calls to Extract-Max sums to O(|V |C). We extract eachvertex once and on l y once so we make |V | calls to Extract-Max. Therefore, each call amortizes toO(|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 pathlength i is stored in bucket i mod C. The correctness of this relies on the fact that the first vertex withpath 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 e very edge weight is less than C, you cannot relax an edge withweight l es s than (k − 1)C + i an d get an edge with weight kC + i. Do i t formall y yourself.3 Single source, Single Target (SPP)If you have a negat ive weight and cycles, you can’t do better than Bellman-Ford since you never knowwhere 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 t h e worst case, this is no bett e r, 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. dfis forward distances, dbis backwards dis t anc e.Termination: Ver t ex w has been popped off 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])2Proof: Let a shortest path from s to t be (u1,u2), (u2,u2),...,(un−1,un)whereu1= s and un= t. Forall shortest paths, we must have at least one edge weight wrong. -minu∈V(df[u]+db[u]) ≥ minu∈V(δ(s, u)+δ(u, t))by the upper bound theoremminu∈V(δ(s, u)+δ(u, t) ≥ δ(s, t))by the triangle inequality.Lemma B: Let v be the vertex that has be en popped off the queue in both the forward and backwardssearches. Let p = �(u1,u2),...,(un−1,un)� be a short est path from s to t (u1= s and un= t). Let ufbe the vertex on this path with the largest dfvalue that has come out of the forward queu e and let ubbe the vertex on this path with the largest dbvalue that has come out of the backwards queue. Theneither uf= ubor uf= ub−1.Proof: By the properties of Dijkstra, we must have that df[uf]=δ(s, uf) and db[ub]=δ(ub,t). Moreover,since ufis the largest vertex to have come out of the forwards queue and ubis the largest vertex to comeout of the backwards queue and p is a shortest path, the following must hold:δ(s, uf) ≤ δ(s, v) (1)δ(s, uf)+w(uf,uf+1) ≥ δ(s, v)(2)δ(ub,t) ≤ δ(v, t) (3)w(ub−1,ub)+δ(ub,t) ≥ δ(v, t) (4)δ(s, uf)+δ(ub,t)+b−1�i=fw(ui,ui+1) ≤ δ(s, v)+δ(v, t) (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, thereforeb−1�i=fw(ui,ui+1) ≤ w(uf,uf+1)+w(ub−1,ub)and we must have either uf= ubor uf= ub−1.Correctness: When a vertex has been popped off the queue of both the forwards and the backwardssearch, δ(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 followsfrom Lemma A.Let p = �(u1,u2),...,(un−1,un)� be a s hor t es t path from s to t. Let ufbe the vertex on this path with thelargest dfthat has been popped off the forward queue and let ubbe vertex on this path wi t h t he lar gestdbthat has been popped off the que ue . Then, by the proof of Dijkstra’s algorit hm, we have relaxed(u1,u2),...,(uf−1,uf), (uf,uf+1) in order (we did the last relaxation whe n we pushed ufonto t he queue).Similarly, we have relaxed (un,un−1),...,(ub,ub−1) in order (in the backwards search). By Lemma B,3uf= ubor uf= ub−1. In the first case, consider vertex uf. We have by the path relaxation propertythat df[uf]=δ(s, uf) and db[uf]=δ(uf,t). Since p is a shortest path, δ(s, t)=δ(s, uf)+δ(uf,t)=df[uf]+db[uf]. Similarly, in the second case, consid er the vertex uf+1. By the path relaxati on property,df[uf+1]=δ(s, uf+1), db[uf+1]=δ(ub,t) and δ(s,
View Full Document
Unlocking...