floyed算法利用python实现

Floyd-Warshall算法是一种用于求解所有节点对之间最短路径的动态规划算法，它适合于处理有向图或无向图中的负权边。在Python中，我们可以按照以下步骤实现这个算法：

def floyd_warshall(graph):
    n = len(graph)  # 图的节点数
    dist = graph.copy()  # 初始化距离矩阵，默认为原邻接矩阵

    # 对所有长度从1到n-1的路径进行迭代
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:  # 如果通过k做中转更优
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist  # 返回最终的最短路径矩阵

# 示例用法：
graph = [[0, 4, float('inf'), float('inf')],
         [float('inf'), 0, 8, 11],
         [float('inf'), float('inf'), 0, 7],
         [float('inf'), 6, float('inf'), 0]]
print(floyd_warshall(graph))

在这个示例中，`graph`是一个二维列表，表示图的邻接矩阵，其中元素值可以是整数（表示权重）或者正无穷大（表示不可达）。运行此函数将返回每个节点对之间的最短路径。