用floyd寻找最短路径

Floyd算法是一种经典的动态规划算法，用于解决任意两点间的最短路径问题。它的基本思想是通过中间点不断更新路径，直到得到最短路径。下面是使用Floyd算法寻找最短路径的步骤：

1. 初始化距离矩阵：将任意两点之间的距离初始化为无穷大，如果两点之间有边相连，则将距离设置为边的权值。

2. 通过中间点更新路径：对于任意两点i和j，如果存在中间点k，使得从点i到点j经过中间点k的路径比直接从点i到点j的路径更短，则更新距离矩阵中i和j之间的距离为i到k的距离加上k到j的距离。

3. 重复进行步骤2，直到所有的中间点都被尝试过为止。

4. 最终得到的距离矩阵即为最短路径。

下面是使用Python实现Floyd算法的示例代码：

INF = float('inf')

def floyd(graph):
    n = len(graph)
    dist = [[0 if i == j else graph[i][j] if graph[i][j] != 0 else 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):
                if dist[i][k] != INF and dist[k][j] != INF and dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 测试
graph = [[0, 1, 3, 0], 
         [1, 0, 1, 2], 
         [3, 1, 0, 1], 
         [0, 2, 1, 0]]
dist = floyd(graph)
for row in dist:
    print(row)

输出结果为：

[0, 1, 2, 3]
[1, 0, 1, 2]
[2, 1, 0, 1]
[3, 2, 1, 0]

其中，dist[i][j]表示从点i到点j的最短距离。