一、算法概述

弗洛伊德算法（Floyd-Warshall Algorithm）是一种用于求解任意两点间最短路径的动态规划算法。它可以在一次运行后得到图中所有节点对之间的最短距离，支持负权边（但不能有负权环）。算法由 Robert Floyd 和 Stephen Warshall 分别独立提出。

二、核心思想

Floyd-Warshall 的核心思想是动态规划 + 中转节点：

设 dist[k][i][j]dist[k][i][j] 表示"从节点 ii 到节点 jj，且只允许经过编号为 11 到 kk 的节点作为中间节点"的最短距离。

状态转移：

$$dist[k][i][j] = \min\big(dist[k-1][i][j],\ dist[k-1][i][k] + dist[k-1][k][j]\big)$$

即：要么不经过 kk，维持原路径；要么经过 kk，用 i→ki \to k 和 k→jk \to j 的最短路径拼接起来。

可以通过滚动数组优化掉第一维，直接在 dist[i][j]dist[i][j] 上进行原地更新：

$$dist[i][j] = \min\big(dist[i][j],\ dist[i][k] + dist[k][j]\big)$$

在最外层循环枚举 kk 即可保证正确性。

三、算法步骤/伪代码

FloydWarshall(图 G):
    // 初始化距离矩阵
    dist[i][j] = 边(i, j) 的权重，若无边则为 +∞
    dist[i][i] = 0

    // 三重循环：枚举中转节点 k
    for k = 0 to V-1:
        for i = 0 to V-1:
            for j = 0 to V-1:
                if dist[i][k] != +∞ and dist[k][j] != +∞:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    // （可选）检测负环
    for i = 0 to V-1:
        if dist[i][i] < 0:
            存在负环

    return dist

路径还原

额外维护一个 next[i][j] 矩阵记录 ii 到 jj 路径上的下一个节点。当 dist[i][j] 因 kk 而被更新时，设置 next[i][j] = next[i][k]。

四、C++ 代码实现

完整可运行的 Floyd-Warshall 实现，包含距离计算、路径还原和传递闭包。

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll INF = LLONG_MAX / 2; // 防溢出

class FloydWarshall {
private:
    int V;
    vector<vector<ll>> dist;
    vector<vector<int>> next; // 路径还原

public:
    FloydWarshall(int n) : V(n),
        dist(n, vector<ll>(n, INF)),
        next(n, vector<int>(n, -1)) {
        // 自己到自己的距离为 0
        for (int i = 0; i < V; ++i) {
            dist[i][i] = 0;
            next[i][i] = i;
        }
    }

    // 添加边
    void addEdge(int u, int v, ll w) {
        dist[u][v] = min(dist[u][v], w); // 有重边时取最小
        next[u][v] = v;
    }

    // 执行 Floyd-Warshall 算法
    // 返回值：是否存在负环
    bool compute() {
        // 枚举中转节点 k
        for (int k = 0; k < V; ++k) {
            for (int i = 0; i < V; ++i) {
                if (dist[i][k] == INF) continue; // 剪枝
                for (int j = 0; j < V; ++j) {
                    if (dist[k][j] == INF) continue;
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k]; // 路径经过 k
                    }
                }
            }
        }

        // 检测负环：对角线出现负数
        for (int i = 0; i < V; ++i) {
            if (dist[i][i] < 0) return true;
        }
        return false;
    }

    // 获取 i 到 j 的最短距离
    ll getDist(int i, int j) { return dist[i][j]; }

    // 还原 i 到 j 的最短路径
    vector<int> getPath(int i, int j) {
        vector<int> path;
        if (dist[i][j] == INF) return path; // 不可达
        int cur = i;
        while (cur != j) {
            if (cur == -1) return {}; // 异常
            path.push_back(cur);
            cur = next[cur][j];
        }
        path.push_back(j);
        return path;
    }

    // 打印距离矩阵
    void printDist() {
        cout << "距离矩阵:" << endl;
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][j] == INF) cout << "INF\t";
                else cout << dist[i][j] << "\t";
            }
            cout << endl;
        }
    }

    // ====== 传递闭包 (Transitive Closure) ======
    // 返回 reachable[i][j]：i 是否可达 j
    vector<vector<bool>> transitiveClosure() {
        vector<vector<bool>> reach(V, vector<bool>(V, false));
        // 初始化
        for (int i = 0; i < V; ++i) {
            reach[i][i] = true;
            for (int j = 0; j < V; ++j) {
                if (dist[i][j] != INF && i != j) {
                    reach[i][j] = true;
                }
            }
        }
        // Floyd 求传递闭包
        for (int k = 0; k < V; ++k) {
            for (int i = 0; i < V; ++i) {
                for (int j = 0; j < V; ++j) {
                    reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
                }
            }
        }
        return reach;
    }
};

// ==================== 主函数 ====================
int main() {
    cout << "========== Floyd-Warshall 任意两点最短路 ==========" << endl;
    FloydWarshall fw(5);

    // 构建示例图（5 节点 0~4）
    fw.addEdge(0, 1, 3);
    fw.addEdge(0, 2, 8);
    fw.addEdge(0, 4, -4);  // 负权边
    fw.addEdge(1, 3, 1);
    fw.addEdge(1, 4, 7);
    fw.addEdge(2, 1, 4);
    fw.addEdge(3, 0, 2);
    fw.addEdge(3, 2, -5);  // 负权边
    fw.addEdge(4, 3, 6);

    bool hasNegCycle = fw.compute();
    if (hasNegCycle) {
        cout << "图中存在负环！" << endl;
    } else {
        fw.printDist();

        cout << "\n路径还原示例:" << endl;
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                if (i == j) continue;
                auto path = fw.getPath(i, j);
                if (!path.empty()) {
                    cout << i << " -> " << j << " (dist=" << fw.getDist(i, j) << "): ";
                    for (int k = 0; k < (int)path.size(); ++k) {
                        if (k > 0) cout << " -> ";
                        cout << path[k];
                    }
                    cout << endl;
                }
            }
        }
    }

    // ====== 传递闭包演示 ======
    cout << "\n========== 传递闭包 (可达性) ==========" << endl;
    FloydWarshall tc(4);
    tc.addEdge(0, 1, 1);
    tc.addEdge(1, 2, 1);
    tc.addEdge(2, 3, 1);
    // 0 -> 1 -> 2 -> 3 形成链，但没有从 0 直接到 3 的边
    tc.compute();

    auto reach = tc.transitiveClosure();
    cout << "可达性矩阵:" << endl;
    cout << "    ";
    for (int j = 0; j < 4; ++j) cout << j << " ";
    cout << endl;
    for (int i = 0; i < 4; ++i) {
        cout << i << " : ";
        for (int j = 0; j < 4; ++j) {
            cout << (reach[i][j] ? "T" : "F") << " ";
        }
        cout << endl;
    }
    // 0 可达 1,2,3（通过传递）
    // 3 不可达 0（单向链）

    return 0;
}

五、复杂度分析

  • 时间复杂度：O(V3)\mathbf{O(V^3)}

    • 三重循环，每重最多 VV 次，共 V3V^3 次迭代
    • 传递闭包（用 bitset 优化后可达 O(V3/w)O(V^3 / w)，其中 ww 为机器字长）

  • 空间复杂度：O(V2)\mathbf{O(V^2)}

    • dist 矩阵：V×VV \times V
    • next 矩阵（路径还原）：V×VV \times V

与其他算法的对比

算法 源点数 时间复杂度 适用场景
Floyd-Warshall 全源 O(V3)O(V^3) VV 较小（≤ 500），求所有点对
Dijkstra（V 次） O(V(V+E)log⁡V)O(V(V+E)\log V) 非负权，EE 较小
Johnson O(V2log⁡V+VE)O(V^2 \log V + VE) 含负权，比 Floyd 更快（稀疏图）

V≤500V \leq 500 时 Floyd 是很好的选择，实现极简。

六、应用场景

场景 说明
任意两点最短路 全源最短路径的经典解法
传递闭包 判断有向图中任意两点之间是否存在路径
最小环 在 Floyd 过程中维护环的权重最小值
图的直径 所有点对最短距离的最大值
中心点选取 到所有点距离之和最小的节点
负环检测 检查 dist[i][i]<0dist[i][i] < 0

七、经典例题

例题1：传递闭包

题目描述：给定一个有向图，对每个节点对 (i,j)(i, j)，判断从 ii 是否能到达 jj。

解法：使用 Floyd 算法求传递闭包。用布尔矩阵 reach[i][j] 代替距离矩阵，三重循环时取 reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])。

上述代码中的 transitiveClosure() 即为完整实现。对于稠密图，还可以用 std::bitset 优化到 O(V3/64)O(V^3 / 64)。

例题2：任意两点最短路

题目描述：给定一个 nn 个节点、mm 条边的有向带权图，回答 qq 次询问，每次询问给出 a,ba, b，求 aa 到 bb 的最短距离。

解法：直接使用 Floyd-Warshall 算法，预处理所有点对距离，然后 O(1)O(1) 回答每次询问。

上述代码中的 FloydWarshall 类即为通用模板。核心步骤：

  1. 读入 n,mn, m 并建图
  2. 调用 compute() 预处理
  3. 对每次询问调用 getDist(a, b) 即可

以下是完整模板：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 2;

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<ll>> dist(n, vector<ll>(n, INF));
    for (int i = 0; i < n; ++i) dist[i][i] = 0;

    for (int i = 0; i < m; ++i) {
        int u, v; ll w;
        cin >> u >> v >> w;
        --u; --v;
        dist[u][v] = min(dist[u][v], w);
    }

    // Floyd-Warshall
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            if (dist[i][k] != INF)
                for (int j = 0; j < n; ++j)
                    if (dist[k][j] != INF)
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    // 处理负环（对角线出现负数）
    bool negCycle = false;
    for (int i = 0; i < n; ++i)
        if (dist[i][i] < 0) { negCycle = true; break; }

    while (q--) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        if (negCycle) {
            cout << "存在负环" << endl;
        } else if (dist[a][b] == INF) {
            cout << "不可达" << endl;
        } else {
            cout << dist[a][b] << endl;
        }
    }
    return 0;
}
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 31ms
  4. Powered by Hydro v5.0.1 Community