用python写一个佛洛依德算法

佛洛依德算法（Floyd Algorithm），也称为插点法，是解决任意两点间的最短路径的经典算法之一。下面是用 Python 实现佛洛依德算法的示例代码：

INF = float('inf')

def floyd(graph):
    n = len(graph)
    dist = [[0 if i == j else graph[i][j] if graph[i][j] else INF for j in range(n)] for i in range(n)]

    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` 是一个二维数组，表示图中每个节点之间的距离。如果两个节点之间没有边相连，则在 `graph` 中用 `0` 或 `None` 表示。`INF` 表示正无穷。

输出的结果是一个二维数组，其中 `dist[i][j]` 表示从节点 i 到节点 j 的最短距离。

例如，可以用以下代码进行测试：

graph = [
    [0, 2, 6, 4],
    [None, 0, 3, None],
    [7, None, 0, 1],
    [5, None, 12, 0]
]

dist = floyd(graph)

for i in range(len(dist)):
    for j in range(len(dist)):
        print(f"{i} -> {j}: {dist[i][j]}")

输出结果：

0 -> 0: 0
0 -> 1: 2
0 -> 2: 5
0 -> 3: 4
1 -> 0: inf
1 -> 1: 0
1 -> 2: 3
1 -> 3: inf
2 -> 0: 7
2 -> 1: inf
2 -> 2: 0
2 -> 3: 1
3 -> 0: 5
3 -> 1: inf
3 -> 2: 10
3 -> 3: 0