数据结构Floyd算法

Floyd算法，也称为Floyd-Warshall算法，是一种用于寻找图中所有顶点对之间最短路径的算法。它适用于有向图和无向图，并且可以处理带权图和无权图。Floyd算法的核心思想是通过动态规划逐步更新图中任意两个顶点之间的最短路径。

以下是Floyd算法的主要步骤：

1. **初始化**：构建一个邻接矩阵，其中每个元素表示图中两个顶点之间的初始距离。如果两个顶点之间有边相连，则矩阵中的元素为边的权重；否则，初始化为一个较大的值（通常用无穷大表示）。

2. **迭代更新**：对于图中的每一个顶点k，检查从顶点i到顶点j的路径是否可以通过顶点k进行优化。如果通过顶点k的路径比当前路径更短，则更新矩阵中的距离。

3. **结果输出**：经过n次迭代（n为图中顶点的数量）后，邻接矩阵中的每个元素表示图中任意两个顶点之间的最短路径长度。

Floyd算法的时间复杂度为O(n^3)，其中n是图中顶点的数量。尽管时间复杂度较高，但Floyd算法在处理稠密图时非常有效。

def floyd_warshall(graph):
    n = len(graph)
    dist = graph.copy()
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

# 示例图
graph = [
    [0, 3, 8, float('inf'), -4],
    [float('inf'), 0, float('inf'), 1, 7],
    [float('inf'), 4, 0, float('inf'), float('inf')],
    [2, float('inf'), -5, 0, float('inf')],
    [float('inf'), float('inf'), float('inf'), 6, 0]
]

shortest_distances = floyd_warshall(graph)
print(shortest_distances)

在这个示例中，图被表示为一个邻接矩阵，`floyd_warshall`函数返回更新后的矩阵，其中每个元素表示图中任意两个顶点之间的最短路径长度。