foobar_4-2_running_with_bunnies.py 文件源码

def floyd(matrix):
    """
    Floyd's algorithm, straight from a textbook. Floyd's algorithm transforms a weight matrix
    into a matrix of shortest paths, such that the shortest path from node M to node N is
    equal to matrix[m][n]

    :return: An array of shortest-path distance calculations.
    """
    n = len(matrix)
    spaths = deepcopy(matrix)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if spaths[i][k] + spaths[k][j] < spaths[i][j]:
                    spaths[i][j] = spaths[i][k] + spaths[k][j]
    return spaths