核心思想

动态规划，求多源最短路径。

对每个中间点 k，尝试用 k 中转更新 i→j 的距离：

dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

模板

const int INF = 0x3f3f3f3f;

// 初始化
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        dis[i][j] = (i == j ? 0 : INF);

// 读边
dis[u][v] = min(dis[u][v], w);

// Floyd
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

关键点

  • k 必须在最外层（DP 阶段，不能换顺序）
  • INF 用 0x3f3f3f3f，避免加法溢出
  • dis[i][i] = 0
  • 重边取 min

复杂度

时间 O(n³)，空间 O(n²)，适合稠密图、n ≤ 500。

扩展

  • 传递闭包：边权视为 1，用 || 和 && 代替 min 和 +
  • 最小环：处理 k 时，dis[i][j] + w[i][k] + w[k][j]（i,j < k）
  • 负环：跑完后若 dis[i][i] < 0 则有负环

对比

Floyd Dijkstra
类型 多源 单源
复杂度 O(n³) O((n+m)log n)
负权 支持 不支持
适用 稠密图 稀疏图