学习首页/图算法/Floyd 最短路径交互演示 · JavaScript

代码与动画 FLOYD–WARSHALL

Floyd 最短路径.

逐个允许顶点作为中间节点，更新任意两点之间的最短距离。

时间 O(V³)空间 O(V²)有向图 · 距离矩阵

原理与执行逻辑

用距离矩阵保存任意两点之间的最短距离，依次允许更多节点作为中间点。处理 k 时比较原路径与经过 k 的两段路径之和。

执行步骤

  1. 对角线初始化为 0，已有边写入权重，未连接位置为 ∞。
  2. 将 k 作为最外层循环，依次选取允许的新中间节点。
  3. 对每对 i、j 更新 d[i][j] = min(d[i][j], d[i][k] + d[k][j])。
  4. 全部中间节点处理后输出完整最短距离矩阵。

关键理解

处理完 k 后，矩阵已考虑中间点取自前 k + 1 个顶点的路径。k 必须位于最外层以维持这个阶段含义；Demo 使用非负权。

简短示例

A→B 为 3、B→C 为 2、A→C 为 9。允许 B 作为中间节点后，A→C 更新为 min(9, 3 + 2) = 5。

代码与执行动画

STEP 0 / 74
Floyd 最短路径
function floyd(n, edges) {  const d = Array.from({length: n}, (_, i) => Array.from({length: n}, (_, j) => i === j ? 0 : Infinity));  for (const {from, to, weight} of edges) d[from][to] = Math.min(d[from][to], weight);  for (let k = 0; k < n; k++) {    for (let i = 0; i < n; i++) {      for (let j = 0; j < n; j++) {        d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);      }    }  }  return d;}
12 行 · 0 个片段标记
ABCDA03∞10B∞02∞C∞∞01D∞4∞0
当前数据正在操作已访问 / 命中标记 / 指针
0

初始化距离矩阵

行是起点，列是终点；已有边写入权重，对角线为 0，其余为 ∞。

配置演示数据

应用后重新生成执行过程，可单步观察结果。

实现说明

Floyd 最短路径的操作规则

固定四个顶点 A–D，输入非负权；矩阵行表示起点，列表示终点，∞ 表示不可达。每步显示 d[i][k] + d[k][j] 与原距离的比较。

对应题目与扩展练习

观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。