# How to compute the predecessor-subgraph in all-pairs-shortest-paths algorithm?

The following slow algorithm (implemented from CLRS book) which runs in $$\Theta(V^4)$$ works fine for computing shortest paths distances:

def extendShortestPath(L, PI, W):
n = len(L)
Lprime = [[float('inf') for x in range(n)] for y in range(n)]
PIprime = [[-1 for x in range(n)] for y in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
if (Lprime[i][j] > L[i][k] + W[k][j]):
Lprime[i][j] = L[i][k] + W[k][j]
PIprime[i][j] = k        # does not work!
PIprime[i][k] = PI[i][k] # does not work!
return Lprime, PIprime

n = len(W)
L = W
PI = [[-1 for x in range(n)] for y in range(n)]
for m in range(1, n):
L, PI = extendShortestPath(L, PI, W)
return L, PI

if __name__ == '__main__':
W = [[float('inf') if x != y else 0 for x in range(5)] for y in range(5)]
W = 3
W = 8
W = -4
W = 1
W = 7
W = 4
W = 2
W = -5
W = 6

But besides computing shortest paths distances, I also need to determine the predecessor vertex of every vertex in the graph for every source vertex. I understand that the relaxing step determines the predecessor. So I added the commented lines to extendShortestPath but it doesn't seem to work. How can I compute the predecessor subgraph?