The Floyd-Warshall algorithm below calculates the shortest path between every pa

Question

The Floyd-Warshall algorithm below 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.

PART 1

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.

PART 2

Suppose we want to modify the Floyd-Warshall algorithm above 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).

- First define the additional table and explain what its entries mean.

- Then, specify the recurrence that will be used to fill in the table. Don’t forget to include a base case. Finally, give the pseudocode for the modified algorithm. Only compute dist and numsp.

Explanation / Answer

for i=1 to N

for j=1 to N

if there is an edge from i to j

dist[0][i][j]=the length of the edge from i to j

else

dist[0][i][j]=INFINITY

for k=1 to N

for i=1 to N

for i=1 to N

for j=1 to N

dist[k][i][j]=min(dist[k-1][i][j],dist[k-1][i][k]+dist[k-1][k][j])

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.