本文最后更新于：2026年11月2日早上

⭕🈸❓ ⭕🅿️❗

0x00. 一切开始之前

前面我们已经讲了用于求单源最短路的 Dijkstra 算法与 Bellman-Ford 算法，但是生活中很多场景并不是只需要单源的最短路，例如在城市交通与导航规划中市政部门往往会需要计算区域内任意两个城市或路口之间的最短通行时间与距离，因此我们会需要一些算法来计算图上所有点之间的最短路径，即全源的最短路

这篇博客主要讲两个计算全源最短路的经典算法：Floyd 算法与 Johnson 算法

Pre. 图的数据结构表示

开始之前我们还是继续重新回顾一下我们用什么样的数据结构表示一张图，一般来说主要有 朴素边表示、邻接表、邻接矩阵 这三种，这里我们重新简单过一遍（ ~~虽然上一篇博客已经过了一遍了~~ ）

朴素边表示，顾名思义就是直接用一个数组存放图里所有的边

#include <tuple>
#include <vector>

typedef std::tuple<int, int, long long> Edge; // u->v, weight
typedef std::vector<Edge> Graph;

邻接表（Adjunct List）可以理解为朴素边表示的一种变体，其将每个节点的边进行单独存放

#include <utility>
#include <vector>

typedef std::pair<int, long long> EdgeOut; // destination, weight
typedef std::vector<std::vector<EdgeOut> > Graph; // Graph[u] stores edges start from u

邻接矩阵（Adjunct Matrix）则使用矩阵（二维数组）来表示两点间是否存在连通关系，适合稠密图，但是对于稀疏图而言会浪费大量存储空间

1
2
3

#include <vector>

typedef std::vector<std::vector<long long> > Graph; // Graph[u][v] is the weight, 0 for no conn

0x01. Floyd-Warshall 算法浅析

Floyd-Warshall 算法（简称 Floyd 算法）由 Robert Floyd 于 1962 年发表（但据悉其本质与 Bernard 与 1959 年以及 Stephen Warshall 于 1962 年发表的用于寻找图的传递闭包的算法相同， ~~反正历史这一块笔者也不是很懂也懒得更深入查证了~~ ），是一种 一次性计算出图上任意两点间最短路径 的算法，且可以处理存在负边权的情况（不能处理负环）

Floyd-Warshall 算法的基本原理是 动态规划 ，我们令 dist[i][j] 为已知的从 i 到 j 的最短距离（在不考虑经过顶点 k 的情况下），当我们将 k 纳入考虑范畴时，从 i 到 j 之间便多出来一条新的路：先从 i 出发到 k，再从 k 出发到 j，此时最短路为 从 i 到 j 的原最短路 与 从 i 到 k 的最短路 + 从 k 到 j 的最短路 之间的最小值，即进行如下更新操作：

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

Floyd-Warshall 算法的核心，便是 不断地对所有的两个点的组合，尝试插入第三个点，看是否能获取更短的路径 （本质上就是不断做松弛操作），由此我们便有如下的 用以计算全源最短路的三重循环 （初始时每个 dist[i][j] 初始化为图上存在连线的两点间距，到自身的距离设为 0，两点间不存在连线则初始化间距为无限大）：

int n; // number of nodes

for (int k = 0; k < n; k++) { // try to add a new k into every i-j pair
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

这便是 Floyd-Warshall 算法，非常简洁明了的三重循环 ，其核心思想本质就是 在最短路上进行松弛操作

Floyd-Warshall 算法为什么是对的？

Floyd-Warshall 算法的核心思路不难理解： dp[i][j] 记录当前从 i 到 j 的最短距离，我们就对于每个 k，都重复遍历一遍所有的点距离，尝试将 k 纳入到 i -> j 的路径中，即如果 i -> k 加上 k -> j 这两段路的总和小于 i -> j 的原长度（(dp[i][k] + dp[k][j]) < dp[i][j] ），则更新 i -> j 的距离为 i -> k -> j

那么问题来了，我们很容易产生这样的疑惑：

为什么 k 要放在最外层循环？
为什么这么算最终能得到正确的最短路结果？

我们先来解决第一个问题，k 放在最外层循环，本质上是 允许每一次多添加一个点 k 作为中转 ，即第一次外层大循环是允许将点 1 纳入到中转，遍历整个图的所有路径查看是否存在一条路径将 1 作为中转会使得整个路径变短，之后的循环便是逐渐将点 2、点 3、…、点 k 给纳入可达的中转范围，即每层外层循环增加一个允许的中转点（第一层循环允许点集合 {1} 作为中转，第二层循环允许点集合 {1,2} 作为中转……）

那么我们会派生一个子问题： 如果将 k 改成内层循环，为什么不对？ 因为 Floyd-Warshall 算法的核心是 动态规划 ，即对于每一次纳入新的点作为中转时， dp[i][j] 都应当是处于一个确定且相同的中间状态： 允许纳入指定的点集合作为中转，而如果 k 改成内层循环，在计算 dp[i][k] + dp[k][j] 时，其状态变得不确定—— 所允许纳入的点集合可能出现不同，这破坏了 dp 的统一含义

一言蔽之，Floyd-Warshall 的正确性（其转移方程 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]) 的正确性），建立在 每一层 k 的完整性上，因为当前层的正确性建立在上一层的完整性上 ，因此只有点 1 的所有结果算完，点 2 的计算才是有意义的，只有点 2 算完，点 3 的计算才是有意义的……以此类推

我们实质上也同时解决了第二个问题：Floyd-Warshall 的正确性，来自于每一层外层循环的完整计算——即 DP 的无后效性

例题：洛谷 B3611 【模板】传递闭包

题目笔者就不完整摘抄了，简而言之要我们通过一个有向图的邻接矩阵，计算其传递闭包（各点间的连通性），这道题目使用 Floyd-Warshall 是可以无脑过的，因为 Floyd-Warshall 是计算全源最短路的算法， 全源最短路都有了，各点之间是否存在连通性也就可以得知了 ，因此最终的解题代码如下：

#include <iostream>

using namespace std;

int main(int argc, char **argv, char **envp)
{
    int n;

    cin >> n;

    int dp[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dp[i][j];
        }
    }


    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][k] != 0 && dp[k][j] != 0) {
                    if (dp[i][j] == 0) {
                        dp[i][j] = dp[i][k] + dp[k][j];
                    } else {
                        dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j]);
                    }
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j] != 0) {
                cout << 1;
            } else {
                cout << 0;
            }

            if (j != (n - 1)) {
                cout << ' ';
            }
        }

        cout << endl;
    }

    return 0;
}

轻松 AC：

0x02. Johnson 算法浅析

Johnson 算法是另外一种能计算全源最短路的算法，由 Donald B. Johnson 于 1977 年提出，其基本思想来源于对单源最短路算法 Dijkstra 的推广，众所周知一个不难想到的求最短路算法是可以直接对所有的点跑一轮最短路算法，而 Dijkstra 是求单源最短路的经典算法（并且已经在 FOCS 2024 上被证明为最优），其时间复杂度可比 Bellman-Ford 好太多了，所以我们不难想到的是可以直接对所有的点跑一轮最短路算法，就能直接得到这个图的全源最短路了——

但是这个办法有个缺陷，众所周知 Dijkstra 无法处理带有负边权的图（因为贪心假设），因此一个非常自然的思路是修改边权（reweight），将负边权变为非负，岂不就能直接应用 Dijkstra 算法了？一个非常自然的思路是给每条边加上一个相同的正数（也就是平移零点），这是一个非常理想的想法——但理想和现实往往总会有一些差距这种朴素的方法实际上会 变更路径长度的相对关系，从而导致最短路关系变更 ，让我们来看下面的这个有向图：

A -> B: -5
B -> D: 2
D -> E: 3
A -> C: 2
C -> E: -1
求 A 到 E 最短路

在初始的图中，A 到 E 有两条路径：A -> B -> D -> E （记为路径1）和 A -> C -> E（记为路径2），路径 1 的长度是 -5 + 2 + 3 = 0 ，路径 2 的长度是 -1 + 2 = 1，因此最短路是路径 1 ，如果我们简单通过加上一个相同正整数的方式进行 reweight 的话，在加上最小正整数 5 的情况下，这个图会变成这样：

A -> B: 0
B -> D: 7
D -> E: 8
A -> C: 7
C -> E: 4
求 A 到 E 最短路

此时路径 1 的长度是 0 + 7 + 8 = 15 ，路径 2 的长度是 4 + 7 = 11 ，而 15 > 11 ， 此时最短路便从路径 1 变为了路径 2 ，因此这样的简单平移数轴的 reweight 是不可行的（悲

如何破局？Johnson 想到了一个妙招：先新建一个连通所有顶点且所有边权都为0的超级源点，在该源点上使用 Bellman-Ford 求其到图中所有点到最短路（设图中有 N 个点，记为数组 h[N]），从而使用这个公式对所有边进行 reweight： new_w(u, v) = old_w(u, v) + (h[u] - h[v]) （即，图中每条边的边权，加上新源点到该边的起始点的最短路，减掉新源点到该边的终点的最短路）

—— 然后就能直接对所有点用 Dijkstra 来求全源最短路了，这就是 Johnson’s Algorithm ，不过需要注意的是，最后求得的最短路结果应当减掉一个起点到终点的 reweight 值，最后写成代码是这个样子：

注：这个算法不能处理负环，所以在超级源点上使用 Bellman-Ford 计算最短路时如果检测到负环应当退出

#include <algorithm>
#include <climits>
#include <utility>
#include <queue>
#include <vector>

using namespace std;

typedef long long int i64;
typedef pair<i64, i64> Edge; // destination, weight
typedef vector<vector<Edge>> Graph;

struct NodeDist {
    i64 node_id;
    i64 dist;

    bool operator>(const NodeDist &n) const {
        return this->dist > n.dist;
    }
};

vector<i64> dijkstra(Graph &graph, i64 src, i64 node_nr)
{
    priority_queue<NodeDist, vector<NodeDist>, greater<NodeDist>> node_min_heap;
    vector<i64> dist(node_nr + 1, LLONG_MAX);

    /* init */
    dist[src] = 0;
    node_min_heap.push({src, 0});

    /* dijkstra loop */
    while (!node_min_heap.empty()) {
        auto victim = node_min_heap.top();
        node_min_heap.pop();

        auto u = victim.node_id;
        auto u_dist = victim.dist;

        /* deduplicate */
        if (dist[u] != u_dist) {
            continue;
        }

        for (auto &edge : graph[u]) {
            auto v = edge.first;
            auto w = edge.second;

            /* relaxation */
            auto new_dist = u_dist + w;
            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                node_min_heap.push({v, new_dist});
            }
        }
    }

    return dist;
}

bool bellman_ford(Graph &graph, i64 src, i64 node_nr, vector<i64> &dist)
{
    
    i64 loop_nr = 0;

    /* init */
    dist[src] = 0;

    /* bellman-ford loop */
    while (loop_nr < (node_nr - 1)) {
        bool has_relax = false;

        for (auto u = 1; u <= node_nr; u++) {
            if (dist[u] == LLONG_MAX) {
                continue;
            }

            for (auto &edge : graph[u]) {
                auto v = edge.first;
                auto w = edge.second;
                auto new_dist = dist[u] + w;
                if (dist[v] > new_dist) {
                    dist[v] = new_dist;
                    has_relax = true;
                }
            }
        }

        if (!has_relax) {
            break;
        }

        loop_nr++;
    }

    if (loop_nr == (node_nr - 1)) {
        /* negative loop */
        bool has_relax = false;
        for (auto u = 1; u <= node_nr; u++) {
            if (dist[u] == LLONG_MAX) {
                continue;
            }

            for (auto &edge : graph[u]) {
                auto v = edge.first;
                auto w = edge.second;
                auto new_dist = dist[u] + w;

                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    has_relax = true;
                }
            }
        }

        if (has_relax) {
            return false;
        }
    }

    return true;
}

bool johnson(Graph &graph, i64 node_nr, vector<vector<i64>> &dist)
{
    i64 new_node = node_nr + 1;
    Graph new_graph(graph);
    vector<i64> h_dist(node_nr + 2, LLONG_MAX);

    dist.resize(node_nr + 1);
    new_graph.resize(node_nr + 2);
    for (i64 v = 1; v <= node_nr; v++) {
        new_graph[new_node].push_back({v, 0});
    }

    if (!bellman_ford(new_graph, new_node, node_nr + 1, h_dist)) {
        return false;
    }

    for (auto u = 1; u <= node_nr; u++) {
        for (auto i = 0; i < graph[u].size(); i++) {
            auto v = graph[u][i].first;
            auto old_w = graph[u][i].second;
            auto new_w = old_w + (h_dist[u] - h_dist[v]);
            new_graph[u][i].second = new_w;
        }
    }

    for (auto u = 1; u <= node_nr; u++) {
        dist[u] = dijkstra(new_graph, u, node_nr);

        for (i64 v = 1; v <= node_nr; v++) {
            if (dist[u][v] != LLONG_MAX) {
                dist[u][v] =  dist[u][v] - h_dist[u] + h_dist[v];
            }
        }
    }

    return true;
}

Johnson’s Algorithm 为什么是对的？

不难看出 Johnson 算法的核心其实在于其独特的 reweight 机制，通过 reweight 在保持边长度相对关系的情况下使得 dijkstra 可用，在完成最短路计算后减掉起点到终点的 reweight 值又能获得正确最短路距离，那么这个 reweight 方式为什么是对的呢？我们一个点一个点进行解析

1. 最后为什么要减掉一个 reweight 值

例如我们考虑图上这样的路径是一条最短路： A -> B -> C -> D ，总长度就是 w_ab + w_bc + w_cd ，当我们建立超级原点进行 reweight 时，这个总长度就变成了 w_ab + h(a) - h(b) + w_bc + h(b) - h(c) + w_cd + h(c) - h(d) ，注意到上一条边的终点会和下一条边的起点相消，于是最后得到的最短路便是 w_ab + w_bc + w_cd + h(a) - h(d) （这种消除形态称为 telescoping）， 这也是为什么最后计算正式的最短路长度时要减掉这样一个 reweight 值的缘故

这也是为什么最短路径不会发生改变的缘故 ，因为在这种计算方式之下，在起始点与终点不变的情况下，中间所有的路径长度都相当于变更了一个相同的值，也就相当于都没变更，这意味着所有路径的相对长度关系都是不变的，自然最短路是不会变的

那么这会引入一个问题：既然路径的长度相对关系是不变的，那么 边之间的相对长度关系会发生变化吗？ 其实是有可能的，但是 Johnson 算法的正确性是来自于同一起点与终点间的整条路径的相对大小不会发生改变，因此路径中间的单条边之间的相对大小的变化，会在整个路径的大小计算上被修正（参见前面的 telescoping 消除），因此问题不大

2. 为什么这样的 reweight 一定是非负的

我们现在来看为什么 reweight 之后边权值一定是非负的，例如对于边 A -> B ，其初始边权值设为为 w_ab ，超级源点 h 通过 bellman-ford 计算出来的到点 A、B 的最短路为 h(a) 与 h(b) ， reweight 之后边权为 w_ab + h(a) - h(b) ，要使该边权值为非负值，则我们有不等式 w_ab + h(a) - h(b) >= 0 ，即 w_ab + h(a) >= h(b) ， 此时我们考虑从 h 出发到 A 再到 B 的路径 h -> A -> B ：

如果这条路径是 h 到 B 的最短路，则有 h(b) = h(a) + w_ab
如果这条路径不是 h 到 B 的最短路，则有 h(b) < h(a) + w_ab

因此，不等式 w_ab + h(a) - h(b) >= 0 成立， 即 reweight 后的边权值一定是非负值

3. 这种算法是否能够使得 Dijkstra 应付负边权的图，成为完美的单源最短路算法？

当然，不过为什么不直接跑 bellman-ford 呢？

例题：洛谷 P5905 【模板】全源最短路（Johnson）

题目就不摘抄了，直接把笔者上面写的 Johnson’s Algorithm 的代码拷贝过来就行，唯一要注意的一个点就是输出不是直接输出最短路长度，而是一个经过计算的特殊值：

#include <algorithm>
#include <climits>
#include <iostream>
#include <utility>
#include <queue>
#include <vector>

using namespace std;

typedef long long int i64;
typedef pair<i64, i64> Edge; // destination, weight
typedef vector<vector<Edge>> Graph;

struct NodeDist {
    i64 node_id;
    i64 dist;

    bool operator>(const NodeDist &n) const {
        return this->dist > n.dist;
    }
};

vector<i64> dijkstra(Graph &graph, i64 src, i64 node_nr)
{
    priority_queue<NodeDist, vector<NodeDist>, greater<NodeDist>> node_min_heap;
    vector<i64> dist(node_nr + 1, LLONG_MAX);

    /* init */
    dist[src] = 0;
    node_min_heap.push({src, 0});

    /* dijkstra loop */
    while (!node_min_heap.empty()) {
        auto victim = node_min_heap.top();
        node_min_heap.pop();

        auto u = victim.node_id;
        auto u_dist = victim.dist;

        /* deduplicate */
        if (dist[u] != u_dist) {
            continue;
        }

        for (auto &edge : graph[u]) {
            auto v = edge.first;
            auto w = edge.second;

            /* relaxation */
            auto new_dist = u_dist + w;
            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                node_min_heap.push({v, new_dist});
            }
        }
    }

    return dist;
}

bool bellman_ford(Graph &graph, i64 src, i64 node_nr, vector<i64> &dist)
{
    
    i64 loop_nr = 0;

    /* init */
    dist[src] = 0;

    /* bellman-ford loop */
    while (loop_nr < (node_nr - 1)) {
        bool has_relax = false;

        for (auto u = 1; u <= node_nr; u++) {
            if (dist[u] == LLONG_MAX) {
                continue;
            }

            for (auto &edge : graph[u]) {
                auto v = edge.first;
                auto w = edge.second;
                auto new_dist = dist[u] + w;
                if (dist[v] > new_dist) {
                    dist[v] = new_dist;
                    has_relax = true;
                }
            }
        }

        if (!has_relax) {
            break;
        }

        loop_nr++;
    }

    if (loop_nr == (node_nr - 1)) {
        /* negative loop */
        bool has_relax = false;
        for (auto u = 1; u <= node_nr; u++) {
            if (dist[u] == LLONG_MAX) {
                continue;
            }

            for (auto &edge : graph[u]) {
                auto v = edge.first;
                auto w = edge.second;
                auto new_dist = dist[u] + w;

                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    has_relax = true;
                }
            }
        }

        if (has_relax) {
            return false;
        }
    }

    return true;
}

bool johnson(Graph &graph, i64 node_nr, vector<vector<i64>> &dist)
{
    i64 new_node = node_nr + 1;
    Graph new_graph(graph);
    vector<i64> h_dist(node_nr + 2, LLONG_MAX);

    dist.resize(node_nr + 1);
    new_graph.resize(node_nr + 2);
    for (i64 v = 1; v <= node_nr; v++) {
        new_graph[new_node].push_back({v, 0});
    }

    if (!bellman_ford(new_graph, new_node, node_nr + 1, h_dist)) {
        return false;
    }

    for (auto u = 1; u <= node_nr; u++) {
        for (auto i = 0; i < graph[u].size(); i++) {
            auto v = graph[u][i].first;
            auto old_w = graph[u][i].second;
            auto new_w = old_w + (h_dist[u] - h_dist[v]);
            new_graph[u][i].second = new_w;
        }
    }

    for (auto u = 1; u <= node_nr; u++) {
        dist[u] = dijkstra(new_graph, u, node_nr);

        for (i64 v = 1; v <= node_nr; v++) {
            if (dist[u][v] != LLONG_MAX) {
                dist[u][v] =  dist[u][v] - h_dist[u] + h_dist[v];
            }
        }
    }

    return true;
}

int main(int argc, char **argv, char **envp)
{
    i64 n, m;

    cin >> n >> m;

    i64 node_nr = n;
    Graph graph(node_nr + 1);

    for (auto i = 0; i < m; i++) {
        i64 u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    vector<vector<i64>> dist(node_nr + 1);

    if (!johnson(graph, node_nr, dist)) {
        cout << -1 << endl;
        return 0;
    }

    for (auto i = 1; i <= n; i++) {
        i64 res = 0;

        for (auto j = 1; j <= n; j++) {
            i64 disij;

            if (i == j) {
                disij = 0;
            } else if (dist[i][j] == LLONG_MAX) {
                disij = 1e9;
            } else {
                disij = dist[i][j];
            }

            res += j * disij;
        }

        cout << res << endl;
    }

    return 0;
}

最后也是一个比较轻松的拿下：

ALGORITHM

#C&C++ #Algorithm #Dynamic Programming #Graph Theory #Floyd Algorithm #Johnson Algorithm

【ALGORITHM.0x06】全源最短路：Floyd-Warshall 算法与 Johnson 算法浅析

http://example.com/2025/11/11/ALGORITHM-0X06-FLOYD_JOHNSON/

作者

arttnba3

发布于

2025年11月11日

许可协议

【OS.0x07】Windows Kernel I：Core Knowledge 上一篇

【ALGORITHM.0x05】单源最短路：Bellman–Ford 算法浅析下一篇