弗洛伊德算法是一种用于求解图中任意两点之间最短路径的经典动态规划算法，具有以下特点：
一、核心思想
通过动态规划递推计算图中所有顶点对之间的最短路径。算法通过中间顶点的引入，逐步更新任意两点间的最短路径长度，最终构建出完整的距离矩阵。
二、算法步骤
初始化 创建一个二维数组 `dp`，其中 `dp[i][j]` 表示从顶点 `i` 到顶点 `j` 的最短路径长度。若 `i` 和 `j` 之间有直接边，则 `dp[i][j]` 初始化为该边的权重；若无直接边，则初始化为无穷大（`inf`）。对于所有顶点 `i`，`dp[i][i]` 初始化为 0。
动态规划递推
对于每一个中间顶点 `k`，遍历所有顶点对 `（i, j）`，更新 `dp[i][j]` 的值：
$$
dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k][j])
$$
该步骤通过引入顶点 `k` 作为中间节点，尝试找到更短的路径。
结果提取
最终 `dp` 矩阵中存储了所有顶点对之间的最短路径长度。若 `dp[i][j]` 仍为无穷大，则表示 `i` 和 `j` 之间无路径。
三、时间复杂度
该算法的时间复杂度为 $O（n^3）$，其中 $n$ 是图中顶点的数量。主要消耗在于三重循环：外层遍历中间顶点 `k`，内层遍历起点 `i` 和终点 `j`。
四、应用场景
多源最短路径： 适用于需要计算图中所有顶点对之间最短路径的场景，如社交网络分析、交通网络规划等。 负权边处理
五、示例
假设有 4 个顶点 A、B、C、D，边权矩阵如下：
```
A B C D
A [0, 10, 30, 100]
B [10, 0, 50, 20]
C [30, 50, 0, 10]
D [100, 20, 10, 0]
```
通过弗洛伊德算法计算后，`dp` 矩阵将更新为：
```
A B C D
A [0, 10, 30, 40]
B [10, 0, 50, 70]
C [30, 50, 0, 10]
D [40, 70, 10, 0]
```
最终 `dp = 40` 表示从 A 到 D 的最短路径长度为 40。
六、改进方向
稀疏图优化：对于稀疏图，可以使用邻接表存储并优化算法，降低时间复杂度。
负权回路检测：在计算过程中若发现 `dp[i][i] < 0`，则说明存在负权回路，需提前终止算法。
弗洛伊德算法凭借其简洁性和通用性，成为图论中最短路径问题的基础算法之一，尤其适用于顶点数量适中的场景。
