Let a simple directed graph D = (V, A) with |V | = n and arc costs ca, a A, be given. Consider the following algorithm:

for all i, j V set d(i, j) := 0 if i = j;

d(i, j) := c(i, j) if (i, j) A;

d(i, j) := else;

for k = 1, . . . , n do

for i = 1, . . . , n do

for j = 1, . . . , n do

if d(i, j) > d(i, k) + d(k, j), then set d(i, j) := d(i, k) + d(k, j).

Extend the FloydWarshall algorithm so that at the end, for all i, j V the variable p(i, j) indicates the predecessor of node j on some least-cost path from i. (This information can be used to reconstruct a least-cost path between any pair of nodes).

Do not need specific code, just write math ideas is fine.