Transcription of Dijkstra’s algorithm: Correctness by induction
1 dijkstra s algorithm : Correctness by inductionWe prove that dijkstra s algorithm (given below for reference) is correct by induction . In the following,Gis the input graph,sis the source vertex,`(uv) is the length of an edge fromutov, andVis the set (G,s)for allu V\{s},d(u) = d(s) = 0R={}whileR6=Vpicku / Rwith smallestd(u)R=R {u}for all verticesvadjacent touifd(v)> d(u) +`(u,v)d(v) =d(u) +`(u,v)Letd(v) be the label found by the algorithm and let (v) be the shortest path distance froms-to-v. Wewant to show thatd(v) = (v) for every vertexvat the end of the algorithm , showing that the algorithmcorrectly computes the distances.
2 We prove this by induction on|R|via the following lemma:Lemma:For eachx R,d(x) = (x).Proof by induction :Base case (|R|= 1):SinceRonly grows in size, the only time|R|= 1 is whenR={s}andd(s) = 0 = (s), which is hypothesis:Letube the last vertex added toR. LetR =R {u}. Our is: for eachx R ,d(x) = (x).Using the :By the inductive hypothesis, for every vertex inR that isn tu, we have the correctdistance label. We need only show thatd(u) = (u) to complete the for a contradiction that the shortest path froms-to-uisQand has length`(Q)< d(u).Qstarts inR and at some leavesR (to get touwhich is not inR ).
3 Letxybe the first edge alongQthatleavesR . LetQxbe thes-to-xsubpath ofQ. Clearly:`(Qx) +`(xy) `(Q).Sinced(x) is the length of the shortests-to- xpath by the ,d(x) `(Qx), giving usd(x) +`(xy) `(Qx).Sinceyis adjacent tox,d(y) must have been updated by the algorithm , sod(y) d(x) +`(xy).Finally, sinceuwas picked by the algorithm ,umust have the smallest distance label:d(u) d(y).Combining these inequalities in reverse order gives us the contradiction thatd(x)< d(x). Therefore, no suchshorter pathQmust exist and sod(u) = (u).This lemma shows the algorithm is correct by applying the lemma forR=V.
