Question

8.1: Show what the arrays will look like after Djikstra's

algorithm completes processing the graph shown in Figure 8.9 on Page 407.

Note that almost all the information you need can be inferred from Figure 8.9e

(show the contents of all three arrays: fringeWgt, parent, and status arrays).

A (partially-filled) example of the parent array is shown in Figure 8.5

at the top of Page 398. HOWEVER, this example array is for Prim's algorithm,

not Dijkstra's. Dijkstra uses a similar set of arrays, but with the important

difference described on Page 410: fringeWgt[v] is now not just the weight of

the single edge ending in v, but the weight of the entire path from s to v.

The following is a screenshot of the textbook

8.3 Single-Source Shortest Paths 407 Tree g Fringe 4 d(A, B) W(BC) 6 Select AG next. (a) The graph (b) An intermediate step ree Friage d(A, G)+WGH) 10 Select GI next (c) An intermediate step: C H was considered but not chosen, to replace GH as a candidate Unseen Tree Fringe Fringe ree (d) Gl is selected. (e) AF was replaced by IF as a candidate Figure 8.9 Anexample for Dijkstra's shortest-path algorithm: The problem is to find a shortest path from A to H.