1. (10 points) Run Dijkstra's algorithm on the directed graph of Figure 24.2 [Text book], first using vertex s as the source and then using vertex z as the source. In the style of Figure 24.6 [Text book], show the d and a values and the vertices in set S after each iteration of the while loop. 6 3 3 3 4 2 so 2 2 7 2 M 4 27 3 5 3 5 5 5 (11 5 5 (11) (11) 6 (a) (b) (c) Figure 24.2 (a) A weighted, directed graph with shortest-path weights from source s. (b) The shaded edges form a shortest-paths tree rooted at the source s. (c) Another shortest-paths tree with the same root. 1 X x X 10 14 10 10 10 9 9 9 2 2 4 2 21 3 21 3 4 S 7 5 5 5 5 oo oo 5 2. 2 2 a) (b) ) 13 10 10 10 3 9 2 21 2 N 21 so 6 so 7 5 5 5 7 5 5 7 2 2. 2 2 2 (f) Figure 24.6 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 mini- mum d value and is chosen as vertex u in line 5. (h)-(f) The situation after each successive iteration of the while loop. The shaded vertex in each part is chosen as vertex u in line 5 of the next iteration. The d values and predecessors shown in part (f) are the final values