全面禁止win11系统更新工具,彻底关闭 Windows 11 更新
2026/1/2 17:30:40
0. 前言：一段只有 5 行代码的“黑魔法”
在图论算法中，Floyd-Warshall（简称 Floyd）是最神奇的存在。
它的核心代码短得令人发指，只有 5 行，甚至比很多人的“Hello World”还短：
//核心代码 for(int k=1;k<=n;k++){//第一层：中转点 for(int i=1;i<=n;i++){//第二层：起点 for(int j=1;j<=n;j++){//第三层：终点 d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } } }初学者往往背下来就完事了。但只要老师稍微追问一句：
“同学，我看你这三层循环都是1到n，那我把k的循环放到最里面（第三层）行不行？”
90% 的同学会愣住：“好像……逻辑上都是遍历所有组合，应该……行吧？”
答案是：绝对不行。
一旦把k放里面，这个算法就从“天才的动态规划”退化成了“甚至不如暴力的错误逻辑”。
今天，我们就把这个算法拆解开，看看它肚子里到底卖的什么药。
1. 核心冲突：为什么k不能在最内层？
我们要反其道而行之，先看看错误的写法会导致什么后果。
假设我们把k放到最里面：
//❌错误示范：k在最里层 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);1.1 一个“反直觉”的失败案例
咱们来推演一个具体的图。
假设路径是：1->2->3。
1->2距离为 2。
2->3距离为 3。
1->3目前不通（距离∞）。
我们的目标是算出d[1][3]=2+3=5。
如果k在最里层，程序是这样跑的：
外层循环固定i=1，中层循环固定j=3。我们正在计算d[1][3]。
内层循环k开始转动，尝试寻找中转点。
当k=2时，程序试图执行：
d[1][3]=min(∞,d[1][2]+d[2][3])
死穴出现了！
在这个时刻，程序需要用到d[1][2]和d[2][3]的值。
d[2][3]是直连边，没问题，是 3。
但是d[1][2]呢？
如果1->2也是一条需要经过其他点（比如1->5->2）才能连通的复杂路径，那么在算出 d[1][3]的这一刻，d[1][2]必须已经算好了。
然而，k 在里层的逻辑是“只扫描一遍”。
如果1->2 的最优路径依赖于节点 5，而节点 5 在循环的后面才出现，或者是 i=1, j=2的遍历顺序在后面，那么此时d[1][2]可能还是∞。
结果：d[1][3]更新失败。你失去了一次连接的机会，而且因为i, j循环只走一次，你永远失去了这个机会。
1.2 错误的本质：贪心 vs 规划
k 在里层：相当于问“我现在能不能找个中间人把i和j连起来？”——这是贪心。它要求中间人两边的关系必须是现成的。
Floyd 的本意：我们需要处理“多跳”路径（比如 A->B->C->D）。这需要动态规划，保证“长路径是由已经确认的最短子路径拼接而成的”。
2. 正确的理解：Floyd 的本质是“层层通关”
把k放在最外层，算法的物理意义就完全变了。它不再是简单的遍历，而是一个“动态规划（DP）”的过程。
2.1 状态定义的奥义
Floyd 的标准状态方程其实是三维的：
dp[k][i][j]
它的含义极其严格：
只允许使用节点1到节点k作为中转站的情况下，从i到j的最短路径。
这个k，代表的不是“第 k 个点”，而是“第 k 个阶段”。
2.2 过程全推演（图解）
想象我们在打一个游戏，地图上有N个城市，但一开始所有中转站都被封锁了，只能走直连航班。
阶段 0 (k=0)：
只能走直连边。1->2有路，2 ->3有路，1->3没路。
阶段 1 (k=1)：【系统广播：1号城市解锁中转权限】
大家开始检查：如果有 i->1->j比原来近，就更新。
此时，所有经过 1 号点的路径都变成了“已知”。
阶段 2 (k=2)：【系统广播：2号城市解锁中转权限】
重点来了！现在允许经过 {1, 2} 中转。
我们要计算 1->3：尝试 1->2->3。
关键点：这里的1->2是什么？
它是“只允许经过 1”的最短路（这是上一阶段 k=1 算出来的成品）。
哪怕1->2实际路径是1->1->2，在 k=1 阶段也早就算好了。
结论：我们在利用“上一版本的完全体”来构建“这一版本的完全体”。
这就是为什么k必须在最外层：它控制着“中转站白名单”的扩充进度。
3. 进阶：为什么三维数组可以“拍扁”成二维？
3.1 你的担心：会不会“自己坑了自己”？
三维公式是这样的：
d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])
我们为了省空间，写成了二维：
d[i][j]=min(d[i][j],d[i][k]+d[k][j])
这时候你肯定会心慌：
程序是顺序执行的。
比如我在算d[1][2]的时候，可能把d[1][k]或者d[k][2]给修改了。
那等到我后面算d[3][4]要用到d[1][k]的时候，拿到的不就是“被修改过的新值”了吗？
我们要的是“上一轮的旧值”，你却给了我“这一轮的新值”，这不就乱套了吗？
3.2 破案：最危险的地方最安全
别慌。我们来看看，在第 k 轮循环里，到底是谁在充当“原料”？ 答案是：d[i][k]（起点到中转站）和d[k][j]（中转站到终点）。
核心问题来了：在第 k 轮循环中，这俩“原料”会发生变化吗？
我们来推演一下 d[i][k]（从 i 去 k）的更新逻辑：
如果不经过 k：距离是旧值。
如果经过 k 中转：距离变成 d[i][k]+d[k][k]。
d[k][k] 是多少？那是“我自己到我自己”的距离，肯定是0。
所以更新公式变成了：
d[i][k]=min(d[i][k],d[i][k]+0)
所以只要没有负权环（Floyd不处理那个），d[i][k] 在第 k 轮里，怎么算都是它自己。它根本就不可能变小，也不可能变大。
3.3 结论
在第 k 轮（中转站是 k）的运算全过程中：
第 k 行的数据（所有 d[k][…]）是静止不动的。
第 k 列的数据（所有 d[…][k]）也是静止不动的。
既然这俩“原料”在这一轮里绝对不会变，那你是读旧数组，还是读正在修改的新数组，结果都是一模一样的。
这就是为什么我们可以大胆地把三维拍扁成二维，没有任何问题。
4. 灵魂追问：k 的循环顺序重要吗？
如果我把最外层循环改成for(int k=n;k>=1;k--)，或者乱序5, 1, 3...，算法还对吗？
答案是：完全正确。
这也解释了 Floyd 的另一个本质：集合论。
最外层循环的本质，是在不断扩充“可用中转点集合”：
空集->{1}->{1,2}->……->{1..n}
空集->{5} ->{5,1}->……->{1..n}
这就好比背包问题：你先判断是否把“物品A”放入背包，还是先判断“物品B”，并不影响最终背包塞满时的最大价值。
只要循环结束时，所有点都曾经当过一次“中转站”，那么所有的路径组合就被穷尽了。
5. 总结
不能死记硬背。下次写 Floyd，脑子里过一遍这三点：
位置：k必须在外层。它是动态规划的阶段循环。
本质：长路径是由短路径拼接的。k在外层，保证了我们在拼i->k->j时，手里的i->k和 k->j已经是算好的“熟食”，而不是“生米”。
空间：三维变二维之所以没 bug，是因为第 k 行和第 k 列在第 k 轮是“静止”的。