The dynamic programming algorithm of Algorithm 1411 computes

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 di- rected graph. Your algorithm should still run in O(n^3) time.

Algorithm AllPairsShortestPaths(G): Input: A simple weighted directed graph G without negative-weight cycles output: A numbering vi, v2, vn of the vertices of G and a matrix D. such that Dli,jl is the distance from vi to vj in G let vi, v2,..., vn be an arbitrary numbering of the vertices of G for i 1 to n do for j 1 to n do ifi j then Doli, il 0 if (vi, vi) is an edge in G then i,vj)) else for k 1 to n do for i 1 to n do for j 1 to n do k-1 return matrix D Algorithm 14.11: A dynamic programming algorithm to compute all-pairs shortest path distances in a digraph without negative cycles.

Solution

The above algorithm is Floyd–Warshall algorithm algorithm which computes only shortest-path distances, not actual paths.

To compute the all shortest paths between each pair of vertices in a di- rected. Modify the algorithm like this.

It returns as output

We have to enter just two line to get path.

if(v_i,v_j) is an edge in G then

after D⁰[i,j]<-w((v_i,v_j)) add P[i,j]<--1; to iinitailize path -1.

and add P[i][j] = k; after assigning minimum distance to D^k[i,j]