The execution of Dijkstra\'s algorithm. The source s is the leftmost vertex. The

Question

The execution of Dijkstra's algorithm. The source s is the leftmost vertex. The shortest path estimates appear within the vertices, and shaded edges indicate predecessor values. Black vertices are in the set S, and white vertices are in the min-priority queue Q = V - S. (a)The situation just before the first iteration of the while loop of lines 4-8. The shaded vertex has the minimum d value and is chosen as vertex u in line 5. (b)-(f) The situation after each successive iteration of the while loop. The shaded vertex in each part is chosen as vertex u in line 5of the next iteration. The d values and predecessors shown in part (f) are the final values.

Explanation / Answer

Applying Dijkstra Algorithm to the given graph:
S.No.   CurrentVertex   Remaining Vertices
1.       z(-, 0)       s(z, 7), x(z, 6), t(-, inf), y(-, inf)
2.       x(z, 6)       s(z, 7), t(-, inf), y(-, inf)
3.        s(z, 7)       t(s, 7 + 10), y(s, 7 + 5)
4.       y(s, 12)       t(y, 12 + 3)
5.       t(y, 15)       -
Therefore, the shortest paths for all the other vertices from z are:
z -> x = 6.
z -> s = 7.
z -> t = 12.
z -> t = 15.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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