全源最短路径 · Zwing's blog

全源最短路径 (All-Pairs Shortest Path, APSP) 问题是指给定一个带权图，求图中任意两点之间的最短路径长度

当然，一个很直接的想法是，对图中的每一个顶点执行一次 SSSP

(在稠密图中，\(O(m)\) = \(O(n^2)\))

	SSSP	APSP
BFS	\(O(n + m) = O(n^2)\)	\(O(n^3)\)
Dijkstra	\(O((n + m)lg n) = O(n^2 lg n)\)	\(O(n^3 lg n)\)
Bellman-Ford	\(O(nm) = O(n^3)\)	\(O(n^4)\)
Topological Sort Variant	\(O(n + m) = O(n^2)\)	\(O(n^3)\)

如何做到最优？有无更优的算法？

Johnson 算法

Johnson 算法是解决含负权边但无负权环的有向图 / 无向图 APSP 的经典算法，核心价值是通过 “边权重重构” 打通 Dijkstra 算法的适用场景，避免多轮 Bellman-Ford 的低效

算法完整步骤:

新增一个虚拟节点，并连接到所有节点，边权均为 0，得到新图
对新增的虚拟节点执行 Bellman-Ford 算法，得到虚拟节点到所有节点的最短路径 \(h\) （若存在负权环直接终止）
按公式重构原图所有边的权重: \(w'(u, v) = h[u] + w(u, v) - h[v]\)
对重构后的图执行 Dijkstra 算法，得到所有节点到所有节点的最短路径 \(d'\)
还原最短路径长度: \(d(u, v) = d[u] + h[v] - h[u]\)

模板题链接

在代码实现上，需要注意因为虚拟节点（原图 1-based，虚拟可设 0 号）的加入而引起边界的改变（n -> n+1）

typedef pair<int, int> pii;
const int INF = 1e9;
struct Edge { int u, v, w; };
int n,m;

void dijkstra(int s, const vector<vector<pii>>& adj, vector<int>& dist)
{
    fill(dist.begin(), dist.end(), INF);
    dist[s] = 0;
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.emplace(0, s);

    while (!pq.empty())
    {
        int u = pq.top().second;
        int curW = pq.top().first;
        pq.pop();
        if (dist[u] < curW) continue;
        for (const auto [v, w] : adj[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
}

bool bellman_ford(int s, vector<Edge> &edges,vector<int> &dist)
{
    dist[s] = 0;
    for (int i = 0; i < n; i++) // 因为虚拟节点的存在变为 n
    {
        bool any_updated = false;
        for (const auto & [u, v, w] : edges)
        {
            if (dist[u] != INF && dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                any_updated = true;
            }
        }
        if (!any_updated) break;
    }

    for (const auto & [u, v, w] : edges)
    {
        if (dist[u] != INF && dist[v] > dist[u] + w)
        {
            return false;
        }
    }
    return true;
}

bool Johnson(const vector<Edge> &edges, vector<vector<pii>> &adj, vector<vector<int>> &dist)
{
    auto newE = edges;
    for (int i = 1; i <= n; i++)
    {
        newE.push_back({0, i, 0}); // 0号虚拟节点加0边
    }
    vector h(n+1, INF);
    if (!bellman_ford(0, newE, h)) return false; // 负环

    for (int u = 1; u <= n; u++)
    {
        for (auto & e : adj[u])
        {
            e.second += h[u] - h[e.first]; // 边权重构
        }
    }
    for (int i = 1; i <= n; i++)
    {
        dijkstra(i, adj, dist[i]); // 逐点 Dijkstra
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j] != INF) // 路径还原
                dist[i][j] -= h[i] - h[j];
        }
    }
    return true;
}

时间复杂度: \(O(NM \log N)\)

最终得到的二维数组 dist[i][j] 即为 \(d(u, v)\)

其中同时用邻接表和边列表略显冗余，若使用 SPFA 优化 Bellman-Ford 算法，可以将邻接表用到底

void dijkstra(int s, const vector<vector<pii>>& adj, vector<int>& dist)
{
    fill(dist.begin(), dist.end(), INF);
    dist[s] = 0;
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.emplace(0, s);

    while (!pq.empty())
    {
        int u = pq.top().second;
        int curW = pq.top().first;
        pq.pop();
        if (dist[u] < curW) continue;
        for (const auto [v, w] : adj[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
}

bool SPFA(int s, const vector<vector<pii>>& adj,vector<int> &dist)
{
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    vector in_queue(n+1,false);
    in_queue[s] = true;
    vector cnt(n+1, 0);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        in_queue[u] = false;
        for (const auto& [v, w] : adj[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;

                if (cnt[v] >= n+1) return false;

                if (!in_queue[v])
                {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    return true;
}

bool Johnson(vector<vector<pii>> &adj, vector<vector<int>> &dist)
{
    auto newAdj = adj;
    for (int i = 1; i <= n; i++)
    {
        newAdj[0].emplace_back(i,0); // 0号虚拟节点加0边
    }
    vector h(n+1, INF);
    if (!SPFA(0, newAdj, h)) return false; // 负环

    for (int u = 1; u <= n; u++)
    {
        for (auto & e : newAdj[u])
        {
            // 边权重构，使用新拷贝的邻接表避免破坏原邻接表
            // 如果不考虑破坏，使用原邻接表也没有任何问题
            e.second += h[u] - h[e.first];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        dijkstra(i, newAdj, dist[i]); // 逐点 Dijkstra
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j] != INF) // 路径还原
                dist[i][j] -= h[i] - h[j];
        }
    }
    return true;
}

Floyd-Warshall 算法

解决全源最短路径问题的经典算法，核心思想是基于动态规划，通过 “依次将每个节点作为中间中转节点，松弛所有节点对的路径”，最终得到任意两个节点之间的最短路径

定义状态 dp[k][i][j] 表示：仅允许使用前 k 个节点（节点编号 1~k）作为中转时，节点 i 到节点 j 的最短路径长度
最终目标是求 dp[n][i][j]（n 为图的总节点数），即允许所有节点作为中转时，i 到 j 的最短路径

对于第 k 个中转节点，i 到 j 的最短路径只有两种可能：

不经过第 k 个节点：最短路径就是 “仅允许前 k-1 个节点中转时的最短路径”，即 dp[k-1][i][j]
经过第 k 个节点：路径为 i→k→j，长度为 dp[k-1][i][k] + dp[k-1][k][j]

因此状态转移方程为：

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

实际实现中无需三维数组：因为 dp[k] 仅依赖 dp[k-1]，可将空间压缩为二维数组，直接在原数组上更新：

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

由 dist[i][j] 初始状态表示 “不允许任何中转节点时，i 到 j 的最短路径长度”，因此初始化规则如下：

自身到自身（i = j）：dist[i][j] = 0
i 和 j 之间有直接边：dist[i][j] = 直接边的权重
i 和 j 之间无直接边（i ≠ j）：dist[i][j] = INF

同时这个算法可以检测负环：若存在负环，则一定存在一个节点 i，使得 dist[i][i] 为负数

const long long INF = 1e9;
int n,m;

bool floyd_warshall(vector<vector<long long>> &dist)
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(dist[i][k] == INF) continue;
            for(int j = 1; j <= n; 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];
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (dist[i][i] < 0) return false;
    return true;
}

int main()
{
    cin >> n >> m; // 还有开快读
    
    vector dist(n+1,vector(n+1,INF));
    for(int i=1;i<=n;i++) dist[i][i] = 0;
    for(int i=1;i<=m;i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        // 处理重边，只取最小
        dist[u][v] = min(dist[u][v],(long long)w);
    }

    if (floyd_warshall(dist))
    {
        // 输出逻辑
    }
    else cout << "-1";
}

注意：在记录 dist 数组时，如果有重边或自环，只取最小

时间复杂度 \(O(n^3)\)

Gemini3.0 Pro Thinking 的选择

看看 \(N\) 的范围：

如果 \(N \le 500\)：无脑选 Floyd。代码好写，不易出错，常数小
如果 \(N > 1000\)：Floyd 必死，必须考虑 Johnson（如果有负权边）或 \(N\) 次 Dijkstra（如果无负权边）

看是否有负权边：

无负权边：直接 \(N\) 次 Dijkstra 即可（不需要 Johnson 的 Bellman-Ford 重赋权步骤），这是最快的
有负权边：\(N\) 小 \(\rightarrow\) Floyd。\(N\) 大 \(\rightarrow\) Johnson

Floyd-Warshall 与传递闭包

Floyd-Warshall 算法可以用来求解图的传递闭包，即判断任意两点之间是否存在路径

此时 dist 数组只需存储布尔值，表示两点之间是否存在路径

但实际上遍历 vector<bool> 会比遍历 vector<int> 慢很多，依然建议用 vector<int>

状态转移方程：dist[i][j] = dist[i][j] || dist[i][k] && dist[k][j]，表示 i 到 j 是否有路径

void floyd_warshall(vector<vector<int>> &dist)
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(!dist[i][k]) continue;
            for(int j = 1; j <= n; j++)
            {
                dist[i][j] = dist[i][j] | dist[i][k] & dist[k][j];
            }
        }
    }
}

而最优版需要使用 std::bitset

void floyd_warshall(bitset<2005> dist[])
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(!dist[i][k]) continue;
            dist[i] = dist[i] | dist[k]; // 直接对整个行按位或
        }
    }
}

std::bitset 的核心优势在于：

空间压缩：每个元素只占 1 bit
时间加速：支持位运算（&, |, ^），一次指令可以并发处理 64 位，常数优化极大（\(O(N/64)\)）

关于 `std::bitset` 的一些补充

定义

#include <bitset> // 头文件
#include <string>
using namespace std;

// 1. 默认构造（全为 0）
bitset<10> b1; // 0000000000

// 2. 使用整数构造
// 会将整数转为二进制，超出部分截断
bitset<10> b2(12); // 12 -> 1100，结果：0000001100

// 3. 使用字符串构造
// 字符串从右向左读，index 0 对应字符串最右边
bitset<10> b3(string("1011")); // 0000001011

访问与修改

可以像操作数组一样操作 bitset，也可以使用成员函数

注意：下标 0 表示最低位（最右边）

操作	语法	说明
访问	`b[i]`	访问第 i 位
检查	`b.test(i)`	检查第 i 位是否为 1（比 `[]` 安全，会检查越界）
置 1（所有）	`b.set()`	将所有位设为 1
置 1（指定）	`b.set(i)`	将第 i 位设为 1
置指定值	`b.set(i, 0)`	将第 i 位设为 0（也可通过 `b.set(i, 1)` 置 1）
重置（所有）	`b.reset()`	将所有位设为 0
重置（指定）	`b.reset(i)`	将第 i 位设为 0
取反（所有）	`b.flip()`	将所有位取反（0变1，1变0）
取反（指定）	`b.flip(i)`	将第 i 位取反

位运算（核心杀器）

和整数一样

查询与统计函数

这些函数在优化图论、背包问题时非常有用。

函数	说明	复杂度
`b.count()`	返回 1 的个数。	极快 (popcount指令)
`b.size()`	返回总位数（即定义时的大小）。	\(O(1)\)
`b.any()`	若存在某一位是 1，返回 `true`。	极快
`b.none()`	若所有位都是 0，返回 `true`。	极快
`b.all()`	(C++11) 若所有位都是 1，返回 `true`。	极快

类型转换

函数	说明
`b.to_ulong()`	转为 `unsigned long` (如果超出范围会抛异常)。
`b.to_ullong()`	转为 `unsigned long long` (C++11)。
`b.to_string()`	转为 `string` (由 ‘0’ 和 ‘1’ 组成)。

高级用法：遍历 `bitset` (GCC 扩展)

在标准 C++ 中，如果你想遍历 bitset 中所有为 1 的位置，通常需要写一个 for 循环检查每一位：

// 慢！O(N)
for(int i = 0; i < N; i++) {
    if(b[i]) { /* do something */ }
}

但在算法竞赛中（通常使用 GCC 编译器），可以使用 _Find_first() 和 _Find_next() 来跳过 0，直接找到下一个 1。这会将复杂度降低到 \(O(\frac{N}{64} + k)\)，其中 \(k\) 是 1 的个数。

#include <bitset>
#include <iostream>
using namespace std;

int main() {
    bitset<100> b;
    b[10] = 1;
    b[55] = 1;
    b[90] = 1;

    // GCC 特有黑科技遍历
    // _Find_first(): 找到第一个 1 的位置
    // _Find_next(i): 找到 i 之后的下一个 1 的位置
    for (int i = b._Find_first(); i < b.size(); i = b._Find_next(i)) {
        cout << i << " "; // 输出 10 55 90
    }
}

注意：这不是 C++ 标准，但在 LeetCode、Codeforces 等使用 GCC/Clang 的平台上可用。

常见应用场景

传递闭包 / Floyd 优化：如你之前的题目，将 \(O(N^3)\) 优化为 \(O(N^3/64)\)
0/1 背包问题优化：当物品价值和体积相同时（即是否能凑出某个和），可以用 bitset 将 DP 转移方程 dp[j] = dp[j] | dp[j-w] 优化为 dp |= (dp << w)
集合运算：快速求两个集合的交集（&）、并集（|）、差集
状态压缩：虽然通常用 int 做状压，但当状态数超过 64 时，必须用 bitset

总结

需要存 true/false 且数量固定？ -> 用 bitset
需要对整行布尔值进行并/交/异或操作？ -> 必须用 bitset
需要动态改变大小？ -> 只能用 vector<bool>（慢）或 vector<char>