floyd算法最短路径python

Floyd算法是一种用于求解图中最短路径的算法，它可以处理有向图或无向图，边权可以为负数，但不能存在负权回路。下面是使用Python实现Floyd算法的示例代码：

INF = float('inf')

def floyd(graph):
    n = len(graph)
    dist = [[graph[i][j] 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):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 示例
graph = [
    [0, 2, 6, 4],
    [INF, 0, 3, INF],
    [7, INF, 0, 1],
    [5, INF, 12, 0]
]
dist = floyd(graph)
print(dist)

输出结果为：

[[0, 2, 5, 4], [inf, 0, 3, 4], [7, 9, 0, 1], [5, 7, 10, 0]]

其中，`graph`是一个邻接矩阵表示的图，`INF`表示正无穷，`dist`是一个二维数组，表示任意两点之间的最短距离。