Floyd 算法简介

Floyd 算法（也叫 Floyd-Warshall 算法）是用来求 图中任意两点的最短路径 的动态规划算法。

  • 适用图：带权图（可有负权边，但不能有负环）
  • 时间复杂度：(O(n^3))
  • 空间复杂度：(O(n^2))

算法原理

假设图有 n 个顶点，编号 1~n。
设 dist[i][j] 表示 从 i 到 j 的最短路距离。

Floyd 算法的核心思路是 逐步引入中间节点：

  1. 初始化：

[ \text{dist}[i][j] = \begin{cases} 0 & i=j \ w(i,j) & i \neq j\text{且有边} \ INF & i \neq j\text{且无边} \end{cases} ]

  1. 动态规划：

[ \text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j]) ]

其中，k 表示允许经过的中间节点，算法从 k = 1 到 k = n 逐步更新 dist[i][j]。

算法特点

  1. 能处理 负边权，但不能有 负环。
  2. 能求 任意两点的最短路。
  3. 简单实现就是三重循环 (O(n^3))。
  4. 也可以同时维护路径信息（next 数组）来输出路径。

OI 风格 C++ 模板

#include <bits/stdc++.h>
using namespace std;

const int N = 505;
const long long INF = 1e18;

long long dist[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w); // 如果有多条边取最小
        // 如果是无向图：
        // dist[v][u] = min(dist[v][u], w);
    }

    // Floyd 三重循环
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    // 输出
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] == INF) cout << "INF ";
            else cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

算法说明

  1. 初始化
    • 对角线为 0
    • 无边的点对设为 INF
    • 有多条边取最小权值
  2. 三重循环
    • 外层 k：允许中间点的编号
    • 中间 i：起点
    • 内层 j：终点
      更新 dist[i][j]，允许路径经过 k 节点。
  3. 判负环
    • 若 dist[i][i] < 0，说明存在负环。
    • 可以在循环中或者循环后判断。
  4. 路径恢复（可选）
    • 用 next[i][j] 记录 i 到 j 的下一个节点。
    • 最终可以回溯输出最短路径。

使用场景

  1. 稠密图：边数接近 (n^2)
  2. 需要求任意两点最短路
  3. 存在负边，但无负环
  4. 需要路径重构

和 Dijkstra / Bellman-Ford 对比

算法 时间复杂度 能处理负边 能判负环 单源/多源
Dijkstra (堆优化) O(E log V) ❌ ❌ 单源
Bellman-Ford O(VE) ✅ ✅ 单源
Floyd O(V^3) ✅ ✅ 多源
  • 稀疏图：Dijkstra > Bellman-Ford
  • 稠密图：Floyd > Dijkstra
  • 负边或负环：Bellman-Ford 或 Floyd

Updated: