Answer Happy

1. In class, we saw pseudocode for Dijkstra's algorithm which returned shortest distances but not shortest paths. In this exercise we'll see how to adapt it to return shortest paths. One way to do that is shown in the pseudocode below: Dijkstra_st_path(G, S, t): for all v in V, set d[v] = Infinity for all v in V, set p[v] = None // we will use the information p[v] to reconstruct the path at the end. d[s] = 0 V [] // D is the list of "done" vertices while F isn't empty: a vertex v in F so that d[v] is minimal for y in x.outgoing_neighbors: d[y] min d[y], d[x] + weight (x,y) ) if d[y] was changed in the previous line, set p[y] F.remove(x) D.add(x) F X = X // use the information in p to reconstruct the shortest path: path [t] current = t while current != s: current p[current] add current to the front of the path return path, d[t] Step through Dijkstra_st_path(G, s. t) on the graph G shown below. Complete the table below (on the next page) to show what the arrays d and p are at each step of the algorithm, and indicate what path is returned and what its cost is. If it is helpful, the LATEXcode for the table is reproduced at the end of the PSET.

u 3 N 5 01 1 9 G t [We are expecting: The following things: . The table below filled out • The shortest path and its cost that the algorithm returns. No justification is required.] d[s] du av d[t] 0 p[s] p p[v] plt) None None None None 0 0 3 2 9 None S None S When entering the first while loop for the first time, the state is: Immediately after the first ele- ment of D is added, the state is: Immediately after the second ele- ment of D is added, the state is: Immediately after the third ele- ment of D is added, the state is: Immediately after the fourth ele- ment of D is added, the state is: