floyd算法代码

Floyd算法，也称为Floyd-Warshall算法，是一种用于寻找图中所有顶点对之间最短路径的动态规划方法。它主要用于解决所有-pair shortest paths (APSP)问题，即在一个加权图中找到任意两个顶点之间的最短路径。

以下是一个使用Python编写的Floyd算法的基本版本，用于处理邻接矩阵表示的图：

def floyd_warshall(graph):
    n = len(graph)
    # 初始化距离矩阵，如果起点到终点没有边，则初始距离为无穷大
    dist = [[graph[i][j] if i != j else float('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):
                # 如果通过中间节点k的路径比直接路径更短，就更新dist[i][j]
                if dist[i][k] + graph[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + graph[k][j]

    return dist

# 使用示例：
graph = [
    [0, 4, float('inf'), 2],
    [4, 0, 1, 8],
    [float('inf'), 1, 0, 7],
    [2, 8, 7, 0]
]
shortest_paths = floyd_warshall(graph)

在这个代码中，`graph`是一个二维列表，其中`graph[i][j]`表示从节点i到节点j的权重。Floyd算法会在运行结束后返回一个新的矩阵`shortest_paths`，其中`shortest_paths[i][j]`是节点i到节点j的最短路径。