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

Transcribed Image Text:

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 D°li, 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"