Recall the algorithm update. procedure update(u, v) element E)/dist(v) = min{dis

Question

Recall the algorithm update. procedure update(u, v) element E)/dist(v) = min{dist(v), dist(u) + phi(u, v)} Suppose that in a graph G = (V, E), with s, t element V and {e_1, e_2, ..., e_k} E, the shortest path from s to t in G consists of the edges e_1, e_2, ..., e_k, in that order. Prove the correctness of the following algorithm that sets dist(t) to its correct shortest distance from procedure update_shortest_path(G, s, t, (e_1, e_2, ..., e_k)) Input: A graph G with edge weights; a start vertex s; an end vertex t; the correct shortest path as a list of edges (G, s, t, (e_1, e_2, ..., e_k)) Output: The shortest distance from s to t. for all u element V dist(u) = infinity dist(s) = 0 for i = 1 ... k: update(e_i) return dist(t)

Explanation / Answer

Here is the proof by Induction method :

Hypothesis : For every traversed vertex 'x' , dist(x) is the shortest distance between 'x' and s(source) . For every un-traversed vertex 'y' , dist(y) is the shorted distance through traveresed vertex only from s to 'y'.

Basis : Let us consider that there is a single vertex in the Graph and which is s (the starting vertex) then assumed hypotheis is a trivial case.

Now let us consider that the Graph has n vertices and assume that the hypothesis is true for n-1 vertices.

Now select an edge xy where y have minimum dist(y) from any untraversed vertices and edge xy is as -

dist(y) = dist(x) + L(x,y) then dist(y) must be shortest distance between s and y since if a shortest path could have existed and if z were the fisrt un-traversed vertex then from the above hypothesis dist(z) < dist(y) would lead to a contradiction. and same as above if a shorted path to 'y' could have been possible without untraversed vertex then dist(y) < dist(x) + L(x,y).

Hence after traversing vertex 'y' the hypothesis will hold true for every untraversed vertices 'z', where dist(z) is the shortest distance of z from s by allowing traversed vertex only, because if a shortest path could have been there without visiting y, the that would have been tracked before itself in between the process which traversing y itself.

Please let me know if anything is not understood.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.