最短路径弗洛伊德算法

弗洛伊德算法，也称为插点法，是一种寻找图中所有节点对之间最短路径的算法。它的时间复杂度为O(n^3)，因此适用于小规模的图。

算法步骤如下：

1.初始化：将每个节点对之间的距离初始化为无穷大，如果两个节点之间有边相连，则将它们之间的距离设为边的权值。

2.对于每个中间节点k，假设k是从节点i到节点j的路径上的一个中间节点，我们尝试更新节点i到节点j的最短路径。如果从节点i到节点j的路径上不经过节点k，那么无需更新，否则计算新路径的长度并更新。

3.重复执行步骤2，直到所有节点对之间的最短路径都被计算出来。

代码实现如下（以邻接矩阵为例）：

def floyd(graph):
    n = len(graph)
    dist = [[float('inf')]*n for i in range(n)]
    # 初始化，将边的权值赋给两个节点之间的距离
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    # 计算每个节点对之间的最短路径
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    return dist

其中，graph是一个n*n的邻接矩阵，表示节点之间的距离，如果两个节点之间没有边相连，则距离设为0。返回值dist也是一个n*n的矩阵，表示每个节点对之间的最短路径。