FloydWarshall.py

def Floyd_Warshall(distance_matrix):
    """
    
    An algorithm for finding shortest paths in a weighted graph (with no negative cycles).

    Source
        - https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
        
    Output:
        - shortest_distance: n**3 matrix from j to k using at most i vertices. 
    """
    
    matrix_length, max_index = len(distance_matrix), len(distance_matrix) - 1
    
    shortest_distance = np.zeros(size = (matrix_length, matrix_length, matrix_length))
    shortest_distance[max_index] = distance_matrix[:]
    

    for i in range(0, matrix_length):
        
        for j in range(0, matrix_length):
            
            for k in range(0, matrix_length):
                
                current_distance = shortest_distance[j][k][max_index] 
                candidate_distance = shortest_distance[j][i][max_index] + shortest_distance[i][k][max_index]
                
                # Sets current distance to candidate distance if shorter.
                if current_distance > candidate_distance:
                    shortest_distance[j][k][max_index] = candidate_distance
                    
                shortest_distance[j][k][i] = shortest_distance[j][k][max_index]
    
    return shortest_distance