引子Dijkstra 回答不了一个问题Dijkstra 是单源算法给我一个起点我告诉你到所有点的最短距离。但很多问题问的是**所有点两两之间——比如 LeetCode 1334哪些城市在阈值距离内可达的邻居最少你要对每一个城市**做一次源点。暴力方案是跑 n 次 DijkstraO(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 到二维滚动完整的状态应该带维度 kd[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 布尔版 Floyd1334 求距离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 能到达 kk 能到达 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]样例验证本地实测输入输出结果n2, [[1,0]], 查询[[0,1],[1,0]][False, True]✅n5, 链式先修 0→1→2→3→4[True,False,True,False]✅n3, [[1,2],[1,0],[2,0]][True,True]✅六、选型与总结6.1 选型表场景推荐复杂度理由n≤500、稠密图、多源FloydO(n³)/O(n²)实现最简单常数小n 大、稀疏图、多源n×Dijkstra(堆)O(n·m·logn)稀疏图明显更快单源、正权Dijkstra(堆)O(m·logn)单源最优负权无负环Floyd / Bellman-FordO(n³) / O(n·m)Floyd 亦可判负环只要可达性Warshall 闭包O(n³)/O(n²)布尔版 Floyd6.2 三个关键结论Floyd 是以中转点扩张的 DPk 的外层顺序、滚动数组的安全性、无负环假设三件事一体理解——这是面试追问的黄金考点[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 WikiFloyd 算法实现细节、选型、负环判定验证说明1334 两组样例、1462 三组样例均于 2026-09-12 本地运行通过Python 3.12。