 也能优雅：三重循环里藏着动态规划（LeetCode 1334 + 1462）)
引子：Dijkstra 回答不了一个问题
Dijkstra 是单源算法：给我一个起点，我告诉你到所有点的最短距离。但很多问题问的是**"所有点两两之间"——比如 LeetCode 1334："哪些城市在阈值距离内可达的邻居最少？"你要对每一个城市**做一次源点。
暴力方案是跑 n 次 Dijkstra（O(n·m·logn)），但 n 小、图稠密时，有一个更简单、更"优雅得让人着迷"的答案：Floyd-Warshall——三行核心循环，O(n³)，把所有点对的最短路一次算完。而且它还是"传递闭包"（LeetCode 1462 先修关系）的天然载体：把min换成or，把+换成and，同一框架两题通吃。
本文拆解三重循环里藏着的动态规划，并给出两题的完整代码与验证。
一、为什么需要"多源"最短路
1.1 单源 vs 多源
单源：一个起点 → 到所有点（Dijkstra / SPFA）
多源：所有点两两之间（Floyd / n×Dijkstra）[3]
1.2 两个高频场景
阈值计数（1334）：对每个城市统计"阈值内可达邻居数"——本质是"这个城市是中心还是边缘"
闭包查询（1462）：课程 A 是不是课程 B 的间接先修——本质是可达性而非距离
这两个问题都要求"全对全"的信息，天然属于 Floyd[1][2]。
二、Floyd 核心：以 k 为中转的动态规划
2.1 状态定义与转移
设d[i][j]= 从 i 到 j 的最短距离。Floyd 的关键洞察：任意一条最短路，要么不经过某个点 k，要么经过 k——于是：
d[i][j] = min( d[i][j], d[i][k] + d[k][j] )外层循环 k 从 0 到 n-1，含义是：逐步允许"前 k 个点"作为中转站。当 k 遍历完，所有点对的最短路就确定了[3]。
INF = float('inf') for k in range(n): # 允许使用 0..k 作为中转点 for i in range(n): for j in range(n): if d[i][k] + d[k][j] < d[i][j]: d[i][j] = d[i][k] + d[k][j]2.2 为什么 k 在最外层
如果 k 在内层，d[i][k]可能还没"允许 k 之前的点中转"，递推就不完整。k 必须在外层——这是 Floyd 正确性的第一道纪律[3][4]。
三、三重循环的正确性：滚动数组的秘密
3.1 三维 DP 到二维滚动
完整的状态应该带维度 k：
d[k][i][j] = min( d[k-1][i][j], # 不用 k 中转 d[k-1][i][k] + d[k-1][k][j] ) # 用 k 中转但代码里我们只开二维，直接原地更新。为什么不会出错？关键在于：第 k 轮更新d[i][j]时读到的d[i][k]和d[k][j]，恰好还是 k-1 轮的旧值——因为"用 k 作为中转点"不会让d[i][k]或d[k][j]变得更小（以 k 为端点，中转 k 是原地绕圈，在非负环假设下无效）[3]。
一句话：滚动数组之所以安全，是因为"中转点 k 不会优化以 k 为端点的路径"——这是 Floyd 最容易被追问的考点[3][4]。
四、LeetCode 1334：阈值距离内邻居最少的城市
4.1 题意与思路
有 n 个城市（0..n-1）和无向带权边，给定 distanceThreshold。对每个城市 i，统计满足
d[i][j] <= distanceThreshold的城市 j 的数量；返回数量最少的城市，若有并列，返回编号最大的那个。
思路三步走：
Floyd 求全源最短路
对每个城市逐行计数
并列取最大编号 →倒序遍历（遇到更小计数才更新）
4.2 完整代码
def findTheCity(n: int, edges: list[list[int]], distanceThreshold: int) -> int: INF = float('inf') d = [[INF] * n for _ in range(n)] for i in range(n): d[i][i] = 0 for u, v, w in edges: d[u][v] = min(d[u][v], w) d[v][u] = min(d[v][u], w) for k in range(n): for i in range(n): for j in range(n): if d[i][k] + d[k][j] < d[i][j]: d[i][j] = d[i][k] + d[k][j] best, city = n + 1, -1 for i in range(n - 1, -1, -1): # 倒序保证并列取最大编号 cnt = sum(1 for j in range(n) if d[i][j] <= distanceThreshold) if cnt < best: best, city = cnt, i return city复杂度：O(n³) 时间 / O(n²) 空间；n≤100 直接过，n≤500 亦可接受[1][4]
五、LeetCode 1462：课程表 IV（传递闭包）
5.1 布尔版 Floyd
1334 求距离，1462 只问可达。把 Floyd 的两个算子换掉：
d[i][j] = min(d[i][j], d[i][k] + d[k][j]) # 距离版 reach[i][j] |= reach[i][k] and reach[k][j] # 布尔版这就是传递闭包（Warshall 算法）——如果 i 能到达 k，k 能到达 j，那么 i 能到达 j[2][4]。
5.2 完整代码
def checkIfPrerequisite(numCourses: int, prerequisites: list[list[int]], queries: list[list[int]]) -> list[bool]: reach = [[False] * numCourses for _ in range(numCourses)] for a, b in prerequisites: reach[a][b] = True for k in range(numCourses): for i in range(numCourses): for j in range(numCourses): if reach[i][k] and reach[k][j]: reach[i][j] = True return [reach[a][b] for a, b in queries]样例验证（本地实测）：
输入 | 输出 | 结果 |
|---|---|---|
n=2, [[1,0]], 查询[[0,1],[1,0]] | [False, True] | ✅ |
n=5, 链式先修 0→1→2→3→4 | [True,False,True,False] | ✅ |
n=3, [[1,2],[1,0],[2,0]] | [True,True] | ✅ |
六、选型与总结
6.1 选型表
场景 | 推荐 | 复杂度 | 理由 |
|---|---|---|---|
n≤500、稠密图、多源 | Floyd | O(n³)/O(n²) | 实现最简单，常数小 |
n 大、稀疏图、多源 | n×Dijkstra(堆) | O(n·m·logn) | 稀疏图明显更快 |
单源、正权 | Dijkstra(堆) | O(m·logn) | 单源最优 |
负权无负环 | Floyd / Bellman-Ford | O(n³) / O(n·m) | Floyd 亦可判负环 |
只要可达性 | Warshall 闭包 | O(n³)/O(n²) | 布尔版 Floyd |
6.2 三个关键结论
Floyd 是"以中转点扩张"的 DP：k 的外层顺序、滚动数组的安全性、无负环假设，三件事一体理解——这是面试追问的黄金考点[3]；
一框架两变体：1334 用距离版，1462 用布尔版，算子一换、问题域就换——理解 Floyd 的抽象结构比背代码重要得多[1][2]；
选型看 n 与稀疏度：O(n³) 不是洪水猛兽，n≤500 时它常比 n 次堆 Dijkstra 更简单可靠；先想规模，再选算法[4]。
学习路线：Dijkstra（单源，第28篇）→Floyd（多源，本篇）→ 传递闭包（1462）→ Johnson 算法（稀疏图多源，SPFA+重标号）→ 最小生成树（第34篇）对照"连通 vs 最短路"两种图优化目标。把 1334 + 1462 亲手跑一遍，你会记住：三重循环不是暴力，是递推。
参考资料
信源编号对应
02-情报.md信源清单。
[1] LeetCode 1334 官方题面（阈值距离内邻居最少的城市）
[2] LeetCode 1462 官方题面（课程表 IV）
[3] CLRS《算法导论》第 25 章：所有结点对的最短路径（Floyd-Warshall 证明）
[4] OI Wiki：Floyd 算法（实现细节、选型、负环判定）
验证说明：1334 两组样例、1462 三组样例均于 2026-09-12 本地运行通过（Python 3.12）。
