GESP 八级 · GESP202609 C++ 八级 第 12 题

在 Floyd 算法的经典三重循环 for (k) for (i) for (j) 中，最外层变量 k 表示（　　）。

Floyd 三重循环的核心是"逐步扩大中间顶点集合"。外层 k 控制允许作为中间点的顶点编号上限，内层 i、j 枚举所有点对。每次迭代后，dist[i][j] 存储的是"仅用编号≤k 的顶点作中间点"的最短距离。这是典型的动态规划：状态由 k 决定，转移用 dist[i][k]+dist[k][j] 更新 dist[i][j]。

B 错在把 k 当成起点——Floyd 求的是全源最短路，起点终点都在内层循环枚举；C 同理，终点是 j 而非 k；D 偷换概念，k 是顶点编号而非路径长度（长度存于 dist 数组）。最阴险的是 A 选项"最大编号"四字，它精准描述了动态规划的状态定义，但很多考生只背"中间点"三个字，忽略"最大编号"这个限定，导致误选其他选项。

考纲定位

本题考查 GESP 八级图论模块中的 Floyd 算法。命题人专门设置这道题，是因为绝大多数考生能背出三重循环结构，却说不清 k 的真实含义——它卡在"只允许编号不超过 k 的顶点作为中间点"这个动态规划状态定义上。这是区分机械记忆与真正理解算法的关键点。

解题思维

看到 Floyd 三重循环，先想"这是动态规划"。Floyd 的本质是逐步扩大中间顶点集合：k=1 时只允许顶点 1 作中间点，k=2 时允许{1,2}，依此类推。内层 i、j 枚举所有点对，对每个点对检查"经过 k 是否更短"：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

用数值验证：假设 n=3，初始 dist 为直接边权。k=1 迭代后，dist[2][3] 可能更新为 dist[2][1]+dist[1][3]；k=2 迭代后，dist[1][3] 可能更新为 dist[1][2]+dist[2][3]（此时 dist[2][3] 已含顶点 1）；k=3 迭代后完成所有点对。可见 k 控制的是"中间顶点集合的上限"，而非起点终点或路径长度。

这一类题的通法是：识别动态规划的状态定义。Floyd 的状态是"(起点，终点，允许中间点集合)"，外层循环控制集合大小，内层循环枚举状态转移。

陷阱拆解

• 选项 B（当前起点）：命题人利用考生对"起点"概念的惯性思维。Floyd 求的是全源最短路，起点终点都在内层循环枚举，k 与起点无关。
• 选项 C（当前终点）：同理，终点是 j，k 只是中间点编号。
• 选项 D（当前最短路径的长度）：这是最阴险的偷换概念。k 是顶点编号，长度存于 dist 数组。命题人故意用"最短路径"这个熟悉词汇包装错误含义。
• 选项 A 的"最大编号"：四字限定精准描述了动态规划状态，但考生容易忽略"最大"二字，误以为 k 只是"当前中间点"。

反命题思维

若把 k 改成"当前允许中间点个数"，算法需改为 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 且 k 从 1 到 n 递增，但这样无法正确更新——因为 dist[i][k] 可能已包含 k 之后的中间点。命题人若改成"当前允许中间点集合"，答案不变；若改成"当前最短路径长度"，则需将 k 改为路径长度维度，变成 Bellman-Ford 式迭代。这些变式都能检验考生是否真正理解 Floyd 的状态定义。