一文彻底搞懂FLOYD算法（弗洛伊德算法）
1. 算法本质
Floyd算法（又称Floyd-Warshall算法）是解决所有顶点对之间最短路径的动态规划算法。
由Robert Floyd于1962年提出（基于Stephen Warshall的传递闭包思想）。
核心思想：动态规划 + 中间点松弛，逐步允许更多顶点作为中转点。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 适用场景与前提
* 适用：带权有向图或无向图（边权可为负，但不能有负权环）。
* 不适用：存在负权环的图（可检测但无法求最短路径）。
* 目标：求任意两点 (i, j) 之间的最短路径长度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 核心思想（动态规划定义）
设 dp[k][i][j] 表示从 i 到 j，只允许经过前 k 个顶点（编号 0~k-1）作为中转点的最短路径长度。
状态转移方程：
* 不经过顶点 k：保持原路径 dp[k-1][i][j]
* 经过顶点 k：拆分为 i→k 和 k→j 两段
空间优化：只需一个二维矩阵 dist[][]，原地更新即可：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 算法步骤（三层循环）
1. 初始化距离矩阵 dist[][]：
* dist[i][i] = 0
* 若存在边 i→j，则 dist[i][j] = weight(i,j)
* 否则 dist[i][j] = INF
2. 三重循环：
3. 检查负权环：若存在 dist[i][i] < 0，则图中有负权环。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 图解示例（手动推演）
图：
顶点：0, 1, 2
边：0→1(3), 0→2(8), 1→2(2), 2→1(-1)（注意负权但不构成负环）
初始距离矩阵：
逐步更新（k=0,1,2）：
中转点k 更新后 dist[1][2] 更新后 dist[2][1] 其他变化 初始 2 -1 - k=0 min(2, ∞+∞)=2 min(-1, ∞+∞)=-1 无 k=1 min(2, 0+2)=2 min(-1, -1+0)=-1 无 k=2 min(2, -1+2)=1 min(-1, 2-1)=-1 dist[1][2] 更新为 1
最终距离矩阵：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 代码实现
PYTHON 实现（基础版）
PYTHON 实现（带路径还原）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++ 实现（基础版）
C++ 实现（带路径还原）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 复杂度分析
指标 复杂度 说明 时间复杂度 O(V³) 三重循环，V 为顶点数 空间复杂度 O(V²) 需要存储距离矩阵 优化可能性 较低 适合稠密图，V ≤ 200~300
> 对于稀疏图，可考虑对每个顶点运行 Dijkstra（堆优化），复杂度 O(V·(E log V))。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 正确性证明（简要）
* 归纳假设：第 k 轮循环后，dist[i][j] 表示从 i 到 j，只允许经过前 k 个顶点（编号 0~k-1）的最短路径。
* 归纳步骤：考虑第 k 轮，新路径要么不经过 k（旧值），要么经过 k（拆分为 i→k 和 k→j，均只使用前 k-1 个顶点）。
* 由动态规划最优子结构性质，可保证最终结果正确。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 与DIJKSTRA算法的对比
特性 Floyd算法 Dijkstra算法 目标 多源（所有点对） 单源（一个起点） 算法类型 动态规划 贪心 时间复杂度 O(V³) O((V+E) log V)（堆优化） 负权边支持 ✅ 支持（无负权环） ❌ 不支持 负权环检测 ✅ 可检测 ❌ 不能 适用场景 稠密图、所有点对最短路 稀疏图、单源最短路 空间 O(V²) O(V+E)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 常见误区与注意事项
* 中转点循环必须在外层：k 在外层是核心，若交换循环顺序会导致错误。
* INF 选择：必须足够大，防止 INF + INF 溢出（C++ 中 1e9 较安全）。
* 有向图与无向图：无向图看作两条方向相反的有向边处理。
* 负权环检测：若最终 dist[i][i] < 0，表示存在负权环，最短路径无定义（可无限减小）。
* 不可达点：保持 INF，表示无路径。
* 重边处理：初始化时取 min 权重。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. 实际应用场景
* 交通网络：求任意两个城市之间的最短行车距离。
* 社交网络：计算用户之间的最短「关系距离」。
* 路由协议：OSPF 中计算全拓扑最短路径（需考虑链路状态）。
* 传递闭包：求有向图的连通性（将边权设为 1，判断可达性）。
* 游戏开发：计算地图中所有点对之间的最短路径。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12. 优化技巧
1. 剪枝优化：若 dist[i][k] == INF，跳过内层循环。
2. 对称矩阵优化：无向图只需计算 j >= i 部分。
3. 使用 short 或 int：根据权重范围选择合适数据类型。
4. 并行化：k 外层无法并行，但 i,j 内层可并行化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
13. 总结
特点 说明 算法类型 动态规划 适用图 有向图/无向图，可含负权边（无负权环） 时间复杂度 O(V³) 空间复杂度 O(V²) 优势 实现简单、支持负权边、多源全路径 劣势 对大规模图（V>500）运行较慢
一句话记忆：
> 三层循环 k,i,j，每次尝试用 k 当中转点来松弛 i→j 的距离，最终得到所有点对的最短路径。
