教我Floyd算法

Floyd算法是一种经典的图论算法，用于计算有向图或者无向图中任意两个顶点之间的最短路径。Floyd算法的核心思想是动态规划，通过不断地更新最短路径的长度，最终得到所有顶点之间的最短路径。

下面是Floyd算法的步骤：

1. 初始化：将每个顶点到自身的距离设为0，如果两个顶点之间有边，则将它们之间的距离设为边的权值，否则设为无穷大。

2. 递推计算：对于每一对顶点i和j，如果存在一个顶点k，使得从i到k再到j的路径比已知的从i到j的路径更短，则更新最短路径长度为i到k再到j的路径长度。

3. 输出结果：最终得到所有顶点之间的最短路径长度矩阵，可以根据需要输出具体的路径信息。

下面是Floyd算法的Python代码实现：

# 用邻接矩阵表示图
INF = float('inf')  # 无穷大
graph = [
    [0, 1, 3, INF],
    [1, 0, INF, 2],
    [3, INF, 0, 4],
    [INF, 2, 4, 0]
]

# Floyd算法
def floyd(graph):
    n = len(graph)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

# 输出最短路径矩阵
floyd(graph)
for i in range(len(graph)):
    for j in range(len(graph)):
        if graph[i][j] == INF:
            print('INF', end=' ')
        else:
            print(graph[i][j], end=' ')
    print()

上述代码中，通过邻接矩阵表示图，其中INF表示两个顶点之间不存在边。在Floyd算法中，通过三重循环依次遍历每一对顶点，并比较当前的最短路径长度和新的路径长度，更新最短路径长度。最后输出最短路径矩阵即可。