【弗洛伊德算法】弗洛伊德算法（Floyd Algorithm），也称为弗洛伊德-沃舍尔算法（Floyd-Warshall Algorithm），是一种用于求解图中所有顶点对之间最短路径的算法。该算法由罗伯特·弗洛伊德（Robert Floyd）于1962年提出，适用于带有权值的有向图或无向图，能够处理正权、负权甚至存在负环的情况。
一、算法概述
弗洛伊德算法的核心思想是动态规划。它通过逐步扩展中间节点的方式，计算每对顶点之间的最短路径。该算法的时间复杂度为 $O(n^3)$，其中 $n$ 是图中顶点的数量。虽然时间复杂度较高，但其结构简单、易于实现，因此在实际应用中广泛使用。
二、算法原理
设图中有 $n$ 个顶点，用邻接矩阵 $D$ 表示图的边权。初始时，$D[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 的直接路径长度；若没有直接边，则设置为无穷大（$\infty$）。算法通过以下步骤进行迭代：
1. 初始化：将邻接矩阵作为初始的距离矩阵。
2. 三重循环：对于每个中间节点 $k$，遍历所有顶点对 $(i, j)$，判断是否可以通过 $k$ 节点获得更短的路径：
$$
D[i][j] = \min(D[i][j], D[i][k] + D[k][j])
$$
3. 输出结果：最终得到的 $D$ 矩阵即为各顶点之间的最短路径距离。
三、适用场景
| 场景 | 是否适用 |
| 有向图 | ✅ |
| 无向图 | ✅ |
| 存在负权边 | ✅ |
| 存在负环 | ❌（可能导致无限循环） |
| 多次查询顶点对最短路径 | ✅ |
四、优缺点对比
| 优点 | 缺点 |
| 可以处理负权边 | 时间复杂度较高（$O(n^3)$） |
| 可以同时求出所有顶点对的最短路径 | 需要额外存储空间 |
| 实现简单，逻辑清晰 | 无法检测负环（需额外处理） |
五、示例说明
假设一个简单的图如下：
```
顶点数：4
邻接矩阵 D：
0 5 ∞ 8
∞ 0 3 ∞
∞ ∞ 0 1
∞ ∞ ∞ 0
```
经过弗洛伊德算法处理后，得到的最短路径矩阵如下：
```
0 5 8 9
∞ 0 3 4
∞ ∞ 0 1
∞ ∞ ∞ 0
```
六、总结
弗洛伊德算法是一种经典的图论算法，适合用于求解所有顶点对之间的最短路径问题。尽管其时间复杂度较高，但在小规模图或需要多次查询最短路径的场景中具有较高的实用价值。理解其基本原理和应用场景有助于更好地在实际项目中加以运用。