Write a Jave program

we put together a set of matrices that would be generated by the Floyd-Warshall algorithm. These matrices give us the value of an optimal solution, but we still want to construct the optimal solution itself: given a pair of vertices vi , vj what would the shortest path through the graph actually be?

APSP Solution. Given a predecessor matrix, print the shortest path for a given source s and destination d. This algorithm should operate on the last predecessor matrix (n)

Pseudocode for this problem is given below.

Print-SP(, i, j)

if i = j

print i

else if ij= NIL

print No path from i to j, bummer!

else

Print-SP(, i, ij)

print j

Sample Input (Right-Hand Columns for Copy-Paste into Source Code)

D(5) =

	1	2	3	4	5
1	0	1	-3	2	-4
2	3	0	-4	1	-1
3	7	4	0	5	3
4	2	-1	-5	0	-2
5	8	5	1	6	0

{ {0, 1, -3, 2, -4},

{3, 0, -4, 1, -1},

{7, 4, 0, 5, 3},

{2, -1, -5, 0, -2},

{8, 5, 1, 6, 0} }