The Floyd-Warshall algorithm calculates the shortest path between every pair of vertices i and j in a graph. In this problem we will assume that the graph is directed and has positive edge lengths.

(a) The pseudocode above computes the length of the shortest path between every two vertices, but it does not compute the prev pointers associated with that shortest path. Suppose we define a new table, prev, where prev(i, j, k) stores the predecessor of j on a shortest-path from i to j using only vertices in {1, . . . , k} as intermediate vertices. Give a recurrence for prev(i, j, k), including a base case. Then give the pseudocode for a modified version of Floyd-Warshall that computes both the dist table and the prev table.

(b) Suppose instead we want to modify the Floyd-Warshall algorithm so that it computes the number of different shortest paths between every two vertices i and j in the graph. Show how to do this by modifying the algorithm to compute an additional table, numsp, with entries of the form numsp(i, j, k).

In your answer to this question, first define the additional table and explain what its entries mean. (In the previous problem, we defined the prev table as follows: Suppose we define a new table, where prev(i, j, k) stores the predecessor of j on a shortest-path from i to j using only vertices in {1, . . . , k} as intermediate vertices. You should give a similar statement for numsp(i, j, k).) Then, specify the recurrence that will be used to fill in the table. Dont forget to include a base case. Finally, give the pseudocode for the modified algorithm. Do not compute prev this time. Just compute dist and numsp.

for i=1 to n: for j l to : dist(i, j,0)=00 dist(i j. 0)ij) for i 1 to n: for all ij)EE for k=1 to n: for j l to n: dist(i, j. k)=min/dist[i, k k11+dist(k, j, k-1), dist(i, j, k-1))