【弗洛伊德算法介绍】弗洛伊德算法（Floyd Algorithm）是一种用于求解图中所有顶点对之间最短路径的算法，也被称为弗洛伊德-沃舍尔算法（Floyd-Warshall Algorithm）。该算法由罗伯特·弗洛伊德（Robert Floyd）和沃什尔（Stephen Warshall）提出，适用于带权图的最短路径计算，尤其在处理具有负权边但无负权环的图时表现良好。
该算法的核心思想是动态规划，通过逐步更新一个距离矩阵来记录任意两点之间的最短路径长度。它不仅能够找到单源最短路径，还能找出所有顶点之间的最短路径，因此在实际应用中非常广泛，如网络路由、交通规划等。
弗洛伊德算法总结
| 项目 | 内容 |
| 算法名称 | 弗洛伊德算法 / 弗洛伊德-沃舍尔算法 |
| 提出者 | Robert Floyd 和 Stephen Warshall |
| 应用场景 | 求解图中所有顶点对之间的最短路径 |
| 数据结构 | 邻接矩阵 |
| 时间复杂度 | O(n³)，n为顶点数 |
| 空间复杂度 | O(n²) |
| 是否支持负权边 | 是，但不能有负权环 |
| 是否可求具体路径 | 可通过额外数组记录前驱节点实现 |
算法步骤简述
1. 初始化距离矩阵：将图的邻接矩阵作为初始的距离矩阵，其中 `dist[i][j]` 表示从顶点 i 到顶点 j 的直接距离。
2. 动态规划更新：对于每一个中间顶点 k，检查是否可以通过 k 来缩短 i 到 j 的路径。即：
`dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`
3. 重复过程：遍历所有可能的中间顶点 k，依次更新所有 i 和 j 的距离。
4. 输出结果：最终得到的矩阵中，`dist[i][j]` 即为从 i 到 j 的最短路径长度。
优点与缺点
| 优点 | 缺点 |
| 可以处理带有负权边的图 | 时间复杂度较高，不适用于大规模图 |
| 能够求解所有顶点对之间的最短路径 | 不适合稀疏图，空间消耗较大 |
| 实现简单，易于理解 | 无法检测负权环（需额外判断） |
示例说明
假设有一个包含 3 个顶点的图，其邻接矩阵如下：
| A | B | C | |
| A | 0 | 5 | ∞ |
| B | 2 | 0 | 7 |
| C | ∞ | 1 | 0 |
经过弗洛伊德算法处理后，最终的最短路径矩阵会显示各顶点之间的最短距离，例如 A 到 C 的最短路径为 A→B→C，总长度为 2 + 7 = 9。
通过以上内容可以看出，弗洛伊德算法在特定场景下具有很高的实用价值，但在面对大规模数据时需谨慎使用。
