(d) Trace the execution of the Floyd-Marshall algorithm for finding all pairs shortest paths on the graph in Fig HW4Q1d.

i. In the style of the textbook show the matrices D(k) , (k) that result after each iteration of the outer loop.

ii. Using the final D and matrices answer the following query: what is the shortest path from 1 to 3 and what is the length of this shortest path?

Question is from algorithm analysis and design

300 41 15 Fig HW4Qld