【弗洛伊德算法介绍】弗洛伊德算法（Floyd Algorithm），也被称为弗洛伊德-沃舍尔算法（Floyd-Warshall Algorithm），是一种用于求解图中所有顶点对之间最短路径的算法。该算法由罗伯特·弗洛伊德（Robert Floyd）和塞缪尔·沃舍尔（Stephen Warshall）共同提出，适用于带有权值的有向图或无向图，能够处理正权值、负权值甚至存在负环的情况。
该算法的核心思想是动态规划，通过逐步更新一个距离矩阵来计算每对顶点之间的最短路径。它的时间复杂度为 O(n³)，其中 n 是图中顶点的数量，因此在处理大规模图时效率较低，但在中小型图中具有较高的实用性。
弗洛伊德算法总结
| 项目 | 内容 |
| 算法名称 | 弗洛伊德算法 / 弗洛伊德-沃舍尔算法 |
| 提出者 | 罗伯特·弗洛伊德 和 塞缪尔·沃舍尔 |
| 应用场景 | 求解图中所有顶点对之间的最短路径 |
| 适用图类型 | 有向图、无向图、带权图（可含负权边） |
| 时间复杂度 | O(n³) |
| 空间复杂度 | O(n²)（存储距离矩阵） |
| 动态规划思想 | 逐步更新两点间的最短路径 |
| 是否处理负环 | 可以检测负环，但无法给出有效路径 |
| 优点 | 实现简单、适用于所有顶点对之间的最短路径计算 |
| 缺点 | 对于大规模图效率较低 |
算法步骤简述
1. 初始化距离矩阵：设 `dist[i][j]` 表示从顶点 i 到顶点 j 的最短距离。初始时，若 i 和 j 直接相连，则赋值为边的权值；若不直接相连，则赋值为无穷大；i 到 i 的距离为 0。
2. 三重循环更新路径：对于每一个中间顶点 k，检查是否可以通过 k 来缩短 i 到 j 的路径。即判断 `dist[i][j] > dist[i][k] + dist[k][j]`，如果是，则更新 `dist[i][j]`。
3. 输出结果：最终得到的 `dist` 矩阵即为所有顶点对之间的最短路径长度。
示例说明
假设有一个包含 3 个顶点的图，其边如下：
- A → B，权值为 2
- B → C，权值为 3
- A → C，权值为 5
初始距离矩阵为：
| A | B | C | |
| A | 0 | 2 | 5 |
| B | ∞ | 0 | 3 |
| C | ∞ | ∞ | 0 |
经过弗洛伊德算法处理后，A 到 C 的最短路径为 A → B → C，总权值为 5，与原路径相同，因此结果不变。
总结
弗洛伊德算法是一个经典而实用的算法，尤其适合需要计算所有顶点对之间最短路径的场景。虽然其时间复杂度较高，但在实际应用中仍然广泛使用，特别是在图结构较小或对性能要求不高的情况下。掌握该算法有助于深入理解图论中的最短路径问题及其解决方法。
