上海充通大学 Dijkstra's Algorithm:Proof of SHANGHAI JLAO TONG UNIVERSITY Correctness Invariant.For each node u e S,d(u)is the length of the shortest s-u path. Pf.(by induction on S) Base case:S =1 is trivial Inductive hypothesis:Assume true for S]=k 1. Let v be next node added to S,and let u-v be the chosenedge. The shortests-u path plus (u,v)is an s-v path of length (v). Consider any s-v path P.We'll see that it's no shorter than (v). Let x-y be the first edge in P that leaves S, and let P'be the subpath to x. P is already too long as soon as it leaves S. l(P)≥l(P)+(x,y)≥d()+l(x,y)≥π(y)≥π() nonnegative inductive defn ofπ) Dijkstra chose v weights hypothesis instead of y 16
16 Dijkstra's Algorithm: Proof of Correctness Invariant. For each node u S, d(u) is the length of the shortest s-u path. Pf. (by induction on |S|) Base case: |S| = 1 is trivial. Inductive hypothesis: Assume true for |S| = k 1. • Let v be next node added to S, and let u-v be the chosen edge. • The shortest s-u path plus (u, v) is an s-v path of length (v). • Consider any s-v path P. We'll see that it's no shorter than (v). • Let x-y be the first edge in P that leaves S, and let P' be the subpath to x. • P is already too long as soon as it leaves S. (P) (P') + (x,y) d(x) + (x, y) (y) (v) nonnegative weights inductive hypothesis defn of (y) Dijkstra chose v instead of y S s y v x P u P
上游充通大粤 Dijkstra's Algorithm:Implementation SHANGHAI JLAO TONG UNIVERSITY For each unexplored node,explicitly maintain π(v)=mind(w)+C。. e=(u,v):u∈S ·Next node to explore=node with minimumπ(). When exploring v,for each incident edgee =(v,w),update π(w)=min{π(w),π(v)+Ce}. Efficient implementation.Maintain a priority queue of unexplored nodes,prioritized byπ(). PQ Operation Dijkstra Array Binary heap d-way Heap Fib heap t Insert n n log n dlogdn 1 ExtractMin n n log n d logdn log n ChangeKey m 1 log n logd n 1 IsEmpty 0 1 1 1 1 Total 2 m log n m log min n m+n log n tIndividual ops are amortized bounds
17 Dijkstra's Algorithm: Implementation For each unexplored node, explicitly maintain • Next node to explore = node with minimum (v). • When exploring v, for each incident edge e = (v, w), update Efficient implementation. Maintain a priority queue of unexplored nodes, prioritized by (v). † Individual ops are amortized bounds PQ Operation Insert ExtractMin ChangeKey Binary heap log n log n log n Fib heap † 1 log n 1 Array n n 1 IsEmpty 1 1 1 Priority Queue Total n m log n m + n log n 2 Dijkstra n n m n d-way Heap d log d n d log d n logd n 1 m log m/n n (v) = min e = (u,v) : u S d(u) + e . (w) = min { (w), (v)+ e }
上浒充通大学 SHANGHAI JLAO TONG UNIVERSITY Dynamic Programming 强 SHANG 1日gG
Dynamic Programming