floyd算法输出最短路径

Floyd算法是一种经典的动态规划算法，用于解决带权图的最短路径问题。它可以求出图中任意两个顶点之间的最短路径，时间复杂度为O(n^3)。下面是使用Python实现Floyd算法输出最短路径的示例代码：

# 定义一个表示正无穷的大数
INF = float('inf')

# 定义Floyd算法函数
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, 1, 4, INF, INF],
         [INF, 0, 2, 5, INF],
         [INF, INF, 0, INF, 3],
         [INF, INF, INF, 0, 1],
         [INF, INF, INF, INF, 0]]
dist = floyd(graph)
for i in range(len(dist)):
    for j in range(len(dist[i])):
        if dist[i][j] == INF:
            print('INF', end=' ')
        else:
            print(dist[i][j], end=' ')
    print()

上述代码中，我们首先定义了一个表示正无穷的大数INF，然后定义了一个floyd函数，该函数接受一个邻接矩阵graph作为输入，返回一个二维数组dist，表示任意两个顶点之间的最短路径。在floyd函数中，我们首先将dist数组初始化为graph数组，然后使用三重循环依次更新dist数组中的元素，最后返回dist数组。在测试代码中，我们定义了一个邻接矩阵graph，并调用floyd函数求解最短路径，最后输出结果。