I’m perusing this article and attempting to put the floyd warshall algorithm into practice. I’m trying to return the matrix containing the antecedents of matrix P and matrix D containing the weights between the shortest routes between points. I think the issue is with my predecessor matrix because it returns none in one instance.
def floydWarshall(self) :
n = len(self._W)
D = copy.deepcopy(self._W)
P = copy.deepcopy(self._W)
for i in range(n) :
for j in range(n) :
if i == j or self._W[i][j] == math.inf :
P[i][j] = None
else :
P[i][j] = i
for k in range(n) :
for i in range(n) :
for j in range(n) :
if D[i][k] + D[k][j] < D[i][j] :
D[i][j] = D[i][k] + D[k][j]
P[i][j] = P[k][j]
return D, P