Floyd-Warshall 全点对算法
求任意两点之间的最短路径
Floyd-Warshall 全点对算法 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
同时求出所有节点对
有时您需要求出每一对节点之间的最短路径，而不只是从一个源点出发的路径。这就是全源点对问题。
认识 Floyd-Warshall
Floyd-Warshall通过三个简洁的嵌套循环，为所有节点对填充完整的距离表，几乎不需要额外准备。
距离矩阵
使用一个矩阵，其中 dist[i][j] 表示从 i 到 j 的已知最小代价。用给定的直接边初始化它。
dist = [[INF] * n for _ in range(n)]设置对角线
每个节点都可以零代价到达自身，因此在开始松弛前，请将对角线上的 dist[i][i] 设为零。
for i in range(n):
dist[i][i] = 0中间节点的思路
关键在于：允许路径经过一个中间节点 k，然后检查经由 k 是否比直接前往更便宜。
循环顺序很重要
外层循环是 k，表示选定的中间节点。内层循环 i 和 j 会针对这个中间节点尝试每一对节点。
for k in range(n):
for i in range(n):
for j in range(n):松弛步骤
对于每一对节点，请通过 k 进行松弛：如果从 i 经过 k 到 j 更短，就将 dist[i][j] 更新为合并后的代价。
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]为什么 k 必须在外层
当 k 处理完时，所有节点对都可以使用编号不超过 k 的中间节点。将k 放在最外层才能保持这一保证正确。
负权边没有问题
Floyd-Warshall 可以接受负权边，但不能处理负环。存在负环时，某个对角线元素会小于零。
运行时间
对 n 个节点执行三层循环会产生O(n^3)的时间复杂度和 O(n^2) 的空间复杂度，因此只有在 n 不超过几百时才实用。
何时选择它
当图规模小且稠密，并且确实需要每一对节点之间的距离，而不是只需要单源距离时，请选择 Floyd-Warshall。
快速检查
在 Floyd-Warshall 中，哪个循环必须位于最外层？
回顾：Floyd-Warshall
初始化矩阵，将对角线设为零，然后按k、i、j循环并通过 k 进行松弛。以 O(n^3) 的复杂度求出所有节点对的最短路径。🧮
常见问题解答
「Floyd-Warshall 全点对算法」课时是免费的吗？
是的 — 「Floyd-Warshall 全点对算法」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「Floyd-Warshall 全点对算法」这节课中我会学到什么？
求任意两点之间的最短路径 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「Floyd-Warshall 全点对算法」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 使用堆实现 Dijkstra
- 使用双端队列实现 0-1 BFS
- Bellman-Ford 与负权边
- Floyd-Warshall 全点对算法