The dynamic programming algorithm of Algorithm 14.11 computes only shortest-path distances, not actual paths. Describe a version of this algorithm that outputs the set of all shortest paths between each pair of vertices in a directed graph. Your algorithm should still run in O(n³) time.

Algorithm 14.11

Algorithm AllPairsShortestPaths(G): Input: A simple weighted directed graph G without negative-weight cycles Output: A numbering v1, v2, ..., Un of the vertices of G and a matrix D, such that D[i, j] is the distance from v to v; in G let v1, v2, ..., Vn be an arbitrary numbering of the vertices of G for i 1 to n do for j +1 to n do if i = j then D[i, i] 0 if (v;, v;) is an edge in G then D[i, j] w(v;, v;)) else Dli, j] - +o for k + 1 to n do for i - 1 to n do for j 1 to n do D*[i, j] - min{Dk-1[i, j], Dk-1[i, k] + Dk-1{k, j]} return matrix D"