弗洛伊德算法的代码逻辑

弗洛伊德（Floyd-Warshall）算法是一种用于求解所有顶点对之间的最短路径的经典动态规划方法，通常用于解决图中的最短路径问题。其基本思想是通过迭代更新每对顶点之间的最短路径，直到所有的最短路径都被找到。

以下是使用 Python 实现的基本逻辑：

def floyd_warshall(graph):
    n = len(graph)  # 图的顶点数
    dist = graph.copy()  # 原始距离矩阵

    # 初始化为0的对角线元素（从每个顶点到自身的距离）
    for i in range(n):
        dist[i][i] = 0

    # 遍历所有可能的中间顶点 k，更新最短路径
    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]:
                    dist[i][j] = dist[i][k] + dist[k][j]

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

# 示例：
graph = [[0, 4, float('inf'), 2],
         [4, 0, 8, 5],
         [float('inf'), 8, 0, 10],
         [2, 5, 10, 0]]
floyd_warshall_result = floyd_warshall(graph)

在这个例子中，`graph`是一个二维数组，表示顶点间的距离。算法首先复制原始距离矩阵，然后逐次检查每对顶点是否可以通过第三个多边形路径变得更短，如果可以，则更新该路径的距离。最后，返回的 `dist` 数组将包含图中所有顶点对之间的最短路径。