弗洛伊德算法python

弗洛伊德算法（Floyd Algorithm），也称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。其时间复杂度为O(n^3)，因此适用于较小规模的图。

以下是使用Python实现弗洛伊德算法的示例代码：

def floyd(graph):
    n = len(graph)
    dist = [[float('inf') for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            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`的`dist`数组，将其初始化为每个节点到另一个节点的距离（如果没有连接，则距离为无穷大）。然后，通过三重循环，依次枚举每个节点，以及通过第k个节点的跳转路径。每一轮循环都更新`dist`数组，最终返回结果。

使用示例：

graph = [[0, 5, float('inf'), 10],
         [float('inf'), 0, 3, float('inf')],
         [float('inf'), float('inf'), 0, 1],
         [float('inf'), float('inf'), float('inf'), 0]]
dist = floyd(graph)
print(dist)

输出结果：

[[0, 5, 8, 9],
 [inf, 0, 3, 4],
 [inf, inf, 0, 1],
 [inf, inf, inf, 0]]

表示每个节点到其他节点的最短路径长度。