Transcription of Dijkstra’s algorithm: Correctness by induction
{{id}} {{{paragraph}}}
Example: bankruptcy
Dijkstra’s algorithm: Correctness by induction
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.
Since d(x) is the length of the shortest s-to-xpath by the I.H., d(x) ‘(Q x), giving us d(x) + ‘(xy) ‘(Q x): Since yis adjacent to x, d(y) must have been updated by the algorithm, so d(y) d(x) + ‘(xy): Finally, since uwas picked by the algorithm, umust have the smallest distance label: d(u) d(y):
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: