Floyd Warshall Algorithm returning None

103 views Asked by At
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

I am trying to implement the floyd warshall algorithm. I am attempting to return the matrix that contains the predecessors of the matrix represented by P and a matrix D that consists of the weights between the shortest paths between vertices. I believe the the problem may be with my predecessor matrix, because it will return none in one case,

0

There are 0 answers