22.3-1

Run Dijkstras algorithm on the directed graph of Figure 22.2, first using vertex s as the source and then using vertex z as the source. In the style of Figure 22.6, show the d and values and the vertices in set S after each iteration of the while loop.

Figure 22.2

Figure 22.6

Figure 22.2 (a) A weighted, directed graph with shortest-path weights from source s. (b) The blue edges form a shortest-paths tree rooted at the source s. (c) Another shortest-paths tree with the same root. Shortest paths are not necessarily unique, and neither are shortestpaths trees. For example, Figure 22.2 shows a weighted, directed graph and two shortest-paths trees with the same root. (a) (v) (c) Figure 22.6 The execution of Dijkstra's algorithm. The source s is the leftmost vertex. The shortest-path estimates appear within the vertices, and blue edges indicate predecessor values. Blue vertices belong to the set S, and tan vertices are in the min-priority queue Q=VS. (a) The situation just before the first iteration of the while loop of lines 6-12. (b)-(f) The situation after each successive iteration of the while loop. In each part, the vertex highlighted in orange was chosen as vertex u in line 7, and each edge highlighted in orange caused a d value and a predecessor to change when the edge was relaxed. The d values and predecessors shown in part (f) are the final values