floyd算法 python

Floyd算法，也称为Floyd-Warshall算法，是一种用于求解图中所有节点间最短路径的动态规划算法。下面是一个用Python实现Floyd算法的示例：

def floyd(graph):
    # 初始化距离矩阵
    dist = graph.copy()
    n = len(graph)
    
    # 更新距离矩阵
    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 = [
    [0, float('inf'), 2, float('inf')],
    [float('inf'), 0, float('inf'), 4],
    [1, float('inf'), 0, float('inf')],
    [float('inf'), 3, float('inf'), 0]
]

result = floyd(graph)
for row in result:
    print(row)

在这个示例中，`graph` 是一个邻接矩阵，表示了图中节点之间的距离。`float('inf')`表示两个节点之间没有直接连接。程序将计算出任意两个节点之间的最短路径，并将结果打印出来。

请注意，这只是Floyd算法的一种实现方式，实际应用中可能会根据具体需求进行修改和优化。