Floyd-Warshall 算法

Floyd-Warshall 算法是一种解决任意两点间最短路径问题的经典动态规划算法。

算法概念

Floyd-Warshall 算法（简称 Floyd 算法）用于寻找给定的加权图中多源点之间最短路径。

主要特点：

全源最短路径：一次运行即可求出图中任意两个节点之间的最短距离。
支持负权边：能够处理边权为负的情况。
不支持负权回路：如果图中存在总权重为负的环路，最短路径可能不存在。
时间复杂度： $O(V^3)$ ，适合顶点数 $V$ 在 500 以内的图。

核心思路：动态规划

Floyd 算法的核心在于通过引入中间节点来逐步优化路径。

假设 $dist(i, j)$ 是从顶点 $i$ 到顶点 $j$ 的当前已知最短距离。我们依次考虑每一个顶点 $k$ 作为中间跳板：对于每一对顶点 $(i, j)$ ，检查：“如果先从 $i$ 走到 $k$ ，再从 $k$ 走到 $j$ ，是否比当前的直接路径 $i \to j$ 更短？”

状态转移方程为：

dist(i, j) = \min(dist(i, j), dist(i, k) + dist(k, j))

代码实现

/**
 * Floyd-Warshall 算法实现
 * @param {number[][]} graph - 邻接矩阵 (INF 表示无边)
 * @returns {number[][]} - 包含所有点对最短路径的矩阵
 */
function floydWarshall(graph) {
    const n = graph.length
    // 拷贝一份矩阵，避免修改原数据
    const dist = Array.from({ length: n }, (_, i) => [...graph[i]])

    // 核心：依次尝试每一个点作为中间点 k
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                // 如果路径 i -> k 和 k -> j 都存在
                if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
                    // 更新 i -> j 的最短路径
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }
    }

    return dist
}

// --- 测试示例 ---
const INF = Infinity
const graph = [
    [0, 3, INF, 7],
    [8, 0, 2, INF],
    [5, INF, 0, 1],
    [2, INF, INF, 0],
]

const shortestPaths = floydWarshall(graph)

console.log('所有点对之间的最短路径矩阵：')
console.table(shortestPaths)

// 验证结果示例：
// 从 0 到 2 的路径：0 -> 1 -> 2 (权重 3 + 2 = 5)
// 从 0 到 3 的路径：0 -> 1 -> 2 -> 3 (权重 3 + 2 + 1 = 6)

LeetCode 题目案例

案例一：最短路径的应用 题目：1334. 阈值距离内邻居最少的城市

题目描述：有 $n$ 个城市，按从 $0$ 到 $n-1$ 编号。给你一个数组 edges，其中 edges[i] = [from_i, to_i, weight_i] 表示城市之间的双向加权边。最后给定一个 distanceThreshold。请你找到一个城市，其在阈值距离内的邻居数量最少。如果有多个这样的城市，则返回编号最大的那个。

解析：我们需要知道任意两点之间的最短距离，然后统计每个城市在阈值范围内的城市数量。

JS 实现：

var findTheCity = function(n, edges, distanceThreshold) {
  // 1. 初始化距离矩阵
  const dist = Array.from({ length: n }, () => Array(n).fill(Infinity));
  for (let i = 0; i < n; i++) dist[i][i] = 0;
  for (const [u, v, w] of edges) {
      dist[u][v] = dist[v][u] = w;
  }

  // 2. Floyd 核心三层循环
  for (let k = 0; k < n; k++) {
      for (let i = 0; i < n; i++) {
          for (let j = 0; j < n; j++) {
              if (dist[i][k] + dist[k][j] < dist[i][j]) {
                  dist[i][j] = dist[i][k] + dist[k][j];
              }
          }
      }
  }

  // 3. 统计并寻找结果
  let minCount = Infinity;
  let res = -1;
  for (let i = 0; i < n; i++) {
      let count = 0;
      for (let j = 0; j < n; j++) {
          if (i !== j && dist[i][j] <= distanceThreshold) {
              count++;
          }
      }
      if (count <= minCount) {
          minCount = count;
          res = i; // 因为 i 是递增的，这里自动满足“编号最大”的要求
      }
  }
  return res;
};

案例二：传递闭包（连通性）的应用 题目：1462. 课程表 IV

题目描述：你总共需要上 $numCourses$ 门课。给你一个数组 prerequisites，其中 prerequisites[i] = [a, b] 表示在修课 b 之前必须先修课 a（直接先修）。再给定 queries，判断 queries[j] = [u, v] 中 $u$ 是否是 $v$ 的先修课（包括间接先修）。

解析：这道题不涉及具体的“权重”，而是考察连通性。如果 $a \to k$ 连通且 $k \to b$ 连通，那么 $a \to b$ 就连通。这就是 Floyd 算法在处理“传递闭包”时的变体。