Floyed算法实现

Floyd算法可以通过三重循环实现，其中外层循环用于遍历中间节点，中间循环用于遍历起点和终点，内层循环用于更新最短路径长度。具体实现代码如下：

def floyd(graph):
    # 初始化距离矩阵
    dist = [[float('inf') for _ in range(len(graph))] for _ in range(len(graph))]
    for i in range(len(graph)):
        for j in range(len(graph)):
            if graph[i][j]:
                dist[i][j] = graph[i][j]
    # 更新距离矩阵
    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

其中，graph是一个邻接矩阵，表示图中各个节点之间的距离。dist是一个二维数组，存储每一对节点之间的最短路径长度。在初始化距离矩阵时，如果graph[i][j]等于0，则表示节点i和节点j之间不存在边；如果graph[i][j]不为0，则表示节点i和节点j之间存在一条边，其权重为graph[i][j]。在更新距离矩阵时，如果从节点i到节点j经过中间节点k的路径长度比直接从i到j的路径长度更短，则更新dist[i][j]的值为dist[i][k]+dist[k][j]。最终，返回dist矩阵即可。

需要注意的是，在实际应用中，需要考虑处理负权边的情况。如果图中存在负权边，则可能会出现负权环，此时Floyd算法将无法正确处理，需要使用其他算法。