对于经典最短路算法的分析

Christmas_Defunct · 2024-08-25 21:32:42 · 算法·理论

前言

现在设想你再考场上，你的面前有一道题。你能很明显地发现，它是最短路的题目。考前你复习了许久，经典最短路算法自然是不会缺席的。考场上你却由于过度紧张发现自己不知道该选什么，该怎么办呢？

本文将会对于这个问题给出详细的解答，如果有误可以指正。

正文

我们所熟知的最短路算法中，分两个类型，单源最短路和多源最短路。

顾名思义，单源最短路可以求出 1 个点到达其余 n-1 个点的距离，而多源最短路则可以求出这 n 个点两两之间的距离。

大多数情况下，我们只需要选择使用单源最短路算法，不过部分题目也会需求多源最短路。这个需要读者视情况分析。

符号解释说明如下。

$s$ 为最短路的源点。 $D(u)$ 为 $s$ 源点到 $u$ 点的**实际**最短路长度。 $dis(u)$ 为 $s$ 点到 $u$ 点的**估计**最短路长度。任何时候都有 $dis(u)\geq D(u)$。特别地，当最短路算法终止时，应有 $dis(u)=D(u)$。其原因是显然的。 $w(u,v)$ 为 $(u,v)$ 这一条边的边权。 ### Floyd-Warshall 算法 Floyd 算法的原理是动态规划，它的思路也十分好理解，从 $i$ 到 $j$ 的最短距离为直接从 $i$ 到 $j$ 的距离和从 $i$ 到 $k$ 再从 $k$ 到 $j$ 中更小者，其代码表示为 `dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])`。我们可以很容易地实现这个代码。

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

int n, m, dis[205][205];

signed main() {
    cin >> n >> m;
    memset(dis, 0x3f, sizeof dis);
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        dis[u][v] = min(dis[u][v], w);
        dis[v][u] = min(dis[v][u], w); //去掉这一行后变为有向图。 
    }
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
    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]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dis[i][j] == 0x3f3f3f3f) cout << "-1 ";
            else cout << dis[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

我们不难发现这个代码的时间复杂度为 O(n^3)，空间复杂度为 O(n^2)，也就是说一般情况下只有当题目中明确指出 n\le200 时才可以使用，这便是 Floyd 特点。一句话总结：写起来快，跑起来慢。

Floyd 虽然跑的慢，但是它可以在负权图中使用，并且可以检测负环。

在此处，我们需要声明一点：所有的图论算法中都不可以强行跑有负环的图，否则两点 i 和 j 之间的距离将会无限减小，只有超级源点可以解决该问题。

Bellman-Ford 算法

Bellman-Ford 是基于松弛操作的最短路算法，其运用范围十分广泛，它可以判断最短路存在与否，同时可以求出有负权的图的最短路。

松弛操作的定义：对于边 (u,v)，松弛操作对应 dis[v] = min(dis[v], dis[u]+ w(u, v))。

这么做的意义十分明显尝试使用 S\to u\to v （其中 S\to u 取最短路）去更新 v 点的最短路长度。

Bellman-Ford 所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止，对于每一轮的循环，时间复杂度为 O(m)。

下面对于循环的次数进行讨论。

共有 n 个点，所以会有 n-1 条最短路，循环次数为 n-1 次，整体代码的复杂度为 O(nm)。

针对负环，Bellman-Ford 有一套处理办法会导致死循环。如果从 S 点出发，抵达一个负环时，松弛操作会无休止地进行下去。

正因如此，Bellman-Ford 算法便可以判断负环。前面我们讲到，循环次数最多为 n-1，所以一旦循环进入了第 n 次，我们可以确定图中出现了负环。

但是，我们这里仅仅对于以 S 为源点是否存在负环，没有对整张图讨论，因此，我们需要一套新的判断负环的方法。

最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman-Ford 算法。

#include <iostream>
#include <climits>

using namespace std;

const int MAXN = 1000; // 最大节点数
const int MAXM = 10000; // 最大边数

struct Edge {
    int u, v, w;
};

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

    Edge edges[MAXM];
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    int dist[MAXN + 1];
    fill(dist, dist + n + 1, INT_MAX);

    dist[1] = 0; // 起点距离为0

    // Bellman-Ford算法
    for (int i = 1; i <= n - 1; ++i) {
        for (int j = 0; j < m; ++j) {
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 输出从节点1到节点n的最短路径长度
    if (dist[n] == INT_MAX) {
        cout << "NO PATH" << endl; // 如果节点n不可达
    } else {
        cout << dist[n] << endl;
    }

    return 0;
}

这个算法的时间复杂度是固定的 O(nm)，然而国内 OI 圈中有对于 Bellman-Ford 的优化版本—— SPFA。

下面将讲讲使用 STL queue 进行优化的 SPFA 算法。

SPFA 算法

SPFA，全称为 Shortest Path Faster Algorithm。既然她都说了 Faster，那么她有多快呢？

SPFA 算法特别适合处理带有负权边的图，并且在随机稀疏图上表现出色，她减少了无用的松弛操作。此时我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。

SPFA 的平均时间复杂度略大于 O(m)，可以理解为 O(k\cdot m)，k 通常情况下是常数级，无需顾虑太多。她的最优复杂度为 O(n)，最劣复杂度则会退化为 O(nm)，与 Bellman-Ford 一样。

#include <iostream>
#include <queue>
#include <climits>

using namespace std;

const int MAXN = 1000; // 假设最多有 1000 个节点
const int INF = INT_MAX;

struct Edge {
    int to, weight;
};

int n, m;
vector<Edge> graph[MAXN + 1]; // 图的邻接表
int dist[MAXN + 1];
bool inQueue[MAXN + 1];

void spfa() {
    fill(dist, dist + n + 1, INF);
    fill(inQueue, inQueue + n + 1, false);

    queue<int> q;
    dist[1] = 0;
    q.push(1);
    inQueue[1] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        for (const Edge& e : graph[u]) {
            int v = e.to;
            int weight = e.weight;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;

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

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

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

    spfa();

    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF)
            cout << "INF" << endl;
        else
            cout << dist[i] << endl;
    }

    return 0;
}

在 2018 年的 NOI 讲评中，SPFA 被冠名“关于 SPFA，她死了。”导致现在很多 OIer 不敢使用 SPFA 和 Bellman-Ford。

然而也会有一些执着的人，为了优化 SPFA 而开发了不同的方式，其中最有名的是 SLF 和 LLL。

下面，我将引用 OI-wiki 中对于各类优化的介绍。

• 堆优化：将队列换成堆，与 Dijkstra 的区别是允许一个点多次入队。在有负权边的图可能被卡成指数级复杂度。
• 栈优化：将队列换成栈（即将原来的 BFS 过程变成 DFS），在寻找负环时可能具有更高效率，但最坏时间复杂度仍然为指数级。
• LLL 优化：将普通队列换成双端队列，每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾，否则插入队首。
• SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。
• D´Esopo-Pape 算法：将普通队列换成双端队列，如果一个节点之前没有入队，则将其插入队尾，否则插入队首。

以上内容都是对于 SPFA 的优化。部分曾经卡死了想要 hack 掉 SPFA 的出题人很久。

不过，fstqwq 最终对于 SPFA 以及其优化内容如何卡掉已经给出了详细的说明。此处借用他在 知乎 上的回答。

• SPFA：一个随机网格图（在网格图中走错一次路可能导致很高的额外开销），或者一个构造过的链套菊花（使得队列更新菊花的次数非常高）即可，推荐构造为网格套菊花。
• LLL：向 1 连接一条权值巨大的边，这样 LLL 就失效了。
• SLF：使用链套菊花的方法，在链上用几个并列在一起的小边权边就能欺骗算法多次进入菊花。
• SLF + 容错：如果边权之和很小的话似乎没有什么很好的办法，因为令边权之和为 W，那么令容错值为 \sqrt W，总复杂度似乎接近 O((V+E)\sqrt W)。不确定这个复杂度对不对，但是 SPFA 确实在边权和小的时候跑得蛮不错的。所以卡法是卡 SLF 的做法，并开大边权，总和最好超过 10^{12}。
• SLF + swap：与卡 SLF 类似，外挂诱导节点即可。
• mcfx：网格图表现优秀，但是菊花图表现很差，但是此优化与 SLF 带容错一起使用有更好的效果，可以使所需要的边权上升许多。。

我们也不得不感谢大佬的点拨：维护一个优先队列在目前来说是需要 \log 的复杂度的，所以低于该复杂度的一定能 hack。

Dijkstra 算法

主体思路如下：将结点分成两个集合：已确定最短路长度的点集（记为 S 集合）的和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。

代码实现中，需初始化 dis[s] = 0，其余赋值为 0x3f。然后重复以下操作。 然后重复这些操作：

1. 从 T 集合中，选取一个最短路长度最小的结点，移到 S 集合中。
2. 对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作。

直到 T 集合为空，算法结束

我们不难看出，整个实现过程中，操作 2 松弛操作无需优化，为 O(m)，重点在于操作 1。

下面是经典方法的时间复杂度。

• 暴力：直接遍历，操作 1 复杂度 O(n^2)，整体复杂度 O(n^2+m)=O(n^2)。
• 二叉堆优化：每成功松弛一条边 (u,v)，就将 v 插入二叉堆中（如果 v 已经在二叉堆中，直接修改相应元素的权值即可），操作 1 直接取堆顶结点即可。共计 O(m) 次二叉堆上的插入（修改）操作，O(n) 次删除堆顶操作，而插入（修改）和删除的时间复杂度均为 O(\log n)，时间复杂度为 O((n+m) \log n) = O(m \log n)。
• 优先队列优化：和二叉堆类似，但使用优先队列时，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是 O(m) 的，时间复杂度为 O(m \log m)。
• Fibonacci 堆：和前面二者类似，但 Fibonacci 堆插入的时间复杂度为 O(1)，故时间复杂度为 O(n \log n + m)，时间复杂度最优。但因为 Fibonacci 堆较二叉堆不易实现，效率优势也不够大，算法竞赛中较少使用。（笔者没有听说过也没有写过 qwq）
• 线段树：和二叉堆原理类似，不过将每次成功松弛后插入二叉堆的操作改为在线段树上执行单点修改，而操作 1 则是线段树上的全局查询最小值。时间复杂度为 O((m+n) \log n)=O(m\log n)。

有人好奇如何选择是否优化：在稀疏图中，m = O(n)，使用二叉堆实现的 Dijkstra 算法较 Bellman-Ford 算法具有较大的效率优势；而在稠密图中，m = O(n^2)，这时候使用暴力做法较二叉堆实现更优。

下面给出暴力版本的 Dijkstra。

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;

const int MAXN = 1e5 + 10;
const int INF = 2147483647;

int n, m, s, t, d[MAXN];
bool vis[MAXN];
vector<PII> G[MAXN];

void dijkstra(int s) {
    for (int i = 0; i <= n; i++) d[i] = INF;
    d[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) if (!vis[j]) {
            if (u == -1 || d[j] < d[u]) {
                u = j;
            }
        }
        if (u == -1 || d[u] >= INF) break;
        vis[u] = true;
        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j].first;
            int w = G[u][j].second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
            }
        }
    }
}

signed main() {
    scanf("%d %d %d %d", &n, &m, &s, &t);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    dijkstra(s);
    printf("%d\n", d[t]);
    return 0;
}

以及 P4779 单源最短路标准解法，即优先队列优化的 Dijkstra，此处给出 dijkstra_slow() 函数方便对比。

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;

const int MAXN = 1e5 + 10;
const int INF = 2147483647;

int n, m, s, d[MAXN];
bool vis[MAXN];
vector<PII> G[MAXN];

void dijkstra_slow(int s) {
    for (int i = 0; i <= n; i++) d[i] = INF;
    d[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) if (!vis[j]) {
            if (u == -1 || d[j] < d[u]) {
                u = j;
            }
        }
        if (u == -1 || d[u] >= INF) break;
        vis[u] = true;
        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j].first;
            int w = G[u][j].second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
            }
        }
    }
}

void dijkstra(int s) {
    for (int i = 0; i <= n; i++) d[i] = INF;
    d[s] = 0;
    priority_queue<pair<int, int>> q;
    q.push({0, s});
    while (q.size()) {
        int u = q.top().second;
        q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].first, w = G[u][i].second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push(make_pair(-d[v], v));
            }
        }
    }
}

signed main() {
    scanf("%d %d %d", &n, &m, &s);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back({v, w});
    }
    //dijkstra_slow(s);
    dijkstra(s);
    for (int i = 1; i <= n; i++) {
        printf("%d ", d[i]);
    }
    puts("");
    return 0;
}

以下是关于 Dijkstra 的正确性证明，参考 OI-Wiki 中的严格证明。

考虑使用数学归纳法，即在所有边权值非负的前提下，讨论 Dijkstra 的正确性。

我们要证明的，就是在执行操作 1 时，取出的结点 u 最短路均已经被确定，即满足 D(u) = dis(u)。

初始时 S = \varnothing，假设成立。

下面考虑反证法。

设 u 点为算法中第一个在加入 S 集合时不满足 D(u) = dis(u) 的点。因为 s 点一定满足 D(u)=dis(u)=0，且它一定是第一个加入 S 集合的点，因此将 u 加入 S 集合前，S\neq\varnothing，如果不存在 s 到 u 的路径，则 D(u) = dis(u) = +\infty，与假设矛盾。

所以原命题成立，即一定存在路径 s \to x \to y \to u，其中 y 为 s \to u 路径上第一个属于 T 集合的点，而 x 为 y 的前驱结点（显然 x \in S）。需要注意的是，可能存在 s = x 或 y = u 的情况，即 s \to x 或 y \to u 可能是空路径，因为我们初始化过 dis[s] = 0。

因为在 u 结点之前加入的结点都满足 D(u) = dis(u)，所以在 x 点加入到 S 集合时，有 D(x) = dis(x)，此时边 (x,y) 会被松弛，从而可以证明，将 u 加入到 S 时，一定有 D(y)=dis(y)。

下面证明 D(u) = dis(u) 成立。仍然考虑反证法在路径 s \to x \to y \to u 中，因为图上所有边边权非负，因此 D(y) \leq D(u)。从而 dis(y) = D(y) \leq D(u)\leq dis(u)。但是因为 u 结点在过程 1 中被取出 T 集合时，y 结点没有被取出 T 集合，因此此时有 dis(u)\leq dis(y)，从而得到 dis(y) = D(y) = D(u) = dis(u)，这与 D(u)\neq dis(u) 的假设矛盾，故假设不成立。

这样我们就证明了为何操作 1 每次取出的点，其最短路均已经被确定。

我们现在证明除了 Dijkstra 的正确性，其中，我们发现了不等式 D(y)\le D(u) 这一个关键不等式。只有当图上任意两点之间的权值 w(i,j)\ge 0 时，满足该条件时才能使用 Dijkstra。

当图上存在负权边时，这一不等式不再成立，Dijkstra 算法的正确性将无法得到保证，算法可能会给出错误的结果。这便是 Dijkstra 的致命缺点。

现在，对于 Dijkstra 的讲解即将步入尾声，我最后想说的是，不难发现，实现 Dijkstra 的方法的原理实际上比较像贪心。所以，需要 Dijkstra 处理的问题无后效性，不能插入多个点进行判断。

Johnson 全源最短路算法

笔者会在开学前更新出对于 Johnson 的解释说明，毕竟是 8 月 24 日刚接触的东西，还有点陌生，主要内容会有关模板题 P5905。

Johnson 全源最短路算法，功能和 Floyd 一样简单粗暴，然而实现却是 Floyd 的无数倍。

这时候你会发现，我们刚刚讲了 Bellman-Ford，Dijkstra 和 SPFA。它们都是单源最短路，可以考虑进行 n 轮，复杂度为原复杂度的 n 倍，可以列举一下。

• Bellman-Ford O(nm\cdot n)=O(n^2m)
• Dijkstra + priority_queue O(m\log m\cdot n)=O(nm\log m)
• SPFA O(k\cdot m\cdot n)=O(k\cdot mn)，其中 k 为一个 \le n 的常数。

可以发现，在不被卡常的情况下，SPFA 算法的效率最高，然而我们注意到 P5905 中有一句话。

部分数据卡 n 轮 SPFA 算法。

也就是说，SPFA 会退化到和 Bellman-Ford 一样，甚至比 Floyd 还要慢。但是题目中的范围也很奇怪：-3\times10^5\le w\le3\times10^5。Dijkstra 不能在负权图上跑的缺陷便被公之于众。那么该怎么办呢？

想要跑负权图，只能用 SPFA，然而 SPFA 和 Dijkstra 都有缺陷，能不能考虑优势互补呢？

仿照 Bellman-Ford 和 SPFA 处理负权图和负环的办法，建立超级源点 0，并使其到其它 n 个点都有一条边，边权都是 0。此时，我们便可以重新标记边权。

我们选择使用 Bellman-Ford 或 SPFA 跑从 0 点到其它点的单源最短路，记作 h_i。这个东西的时间复杂度最劣情况为 O(nm)。

假如 u\to v 之间存在一条边，其原边权为 w，那么应将其修改为 w+h_u-h_v。

这样，便解决了 Dijkstra 不能跑负权图的缺陷。接下来就是喜闻乐见的 n 轮 Dijkstra，时间复杂度为 O(nm\log m)。

整体算法的时间复杂度不难计算 O(nm+nm\log m)=O(nm\log m)。

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

const int INF = 2147483647;

struct edge { int v, w, next; } e[10005];

struct node {
    int dis, id;
    bool operator<(const node& a) const { return dis > a.dis; }
    node(int d, int x) : dis(d), id(x) {}
};

int head[5005], vis[5005], t[5005];
int cnt, n, m;
int h[5005], dis[5005];

void addedge(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

bool spfa(int s) {
    queue<int> q;
    memset(h, 63, sizeof(h));
    h[s] = 0;
    vis[s] = 1;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;

        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (h[v] > h[u] + e[i].w) {
                h[v] = h[u] + e[i].w;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                    t[v]++;
                    if (t[v] == n + 1) return false;
                }
            }
        }
    }
    return true;
}

void dijkstra(int s) {
    priority_queue<node> q;
    for (int i = 1; i <= n; i++) dis[i] = INF;
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push(node(0, s));

    while (!q.empty()) {
        int u = q.top().id;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;

        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (!vis[v]) q.push(node(dis[v], v));
            }
        }
    }
}

signed main() {
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addedge(u, v, w);
    }

    for (int i = 1; i <= n; i++) {
        addedge(0, i, 0);
    }

    if (!spfa(0)) {
        cout << -1 << endl;
        return 0;
    }

    for (int u = 1; u <= n; u++) {
        for (int i = head[u]; i; i = e[i].next) {
            e[i].w += h[u] - h[e[i].v];
        }
    }

    for (int i = 1; i <= n; i++) {
        dijkstra(i);
        for (int j = 1; j <= n; j++) {
            if (dis[j] == INF) cout << -1 << ' ';
            else cout << dis[j] + h[j] - h[i] << ' ';
        }
        putchar('\n');
    }

    return 0;
}

最后，将证明 Johnson 全源最短路的正确性，严格证明如下。

这里我们仍然参考 OI-Wiki 中的严格证明过程，有修改。

在讨论这个问题之前，我们先讨论一个物理概念——势能。

诸如重力势能，电势能这样的势能都有一个特点，势能的变化量只和起点和终点的相对位置有关，而与起点到终点所走的路径无关。

势能还有一个特点，势能的绝对值往往取决于设置的零势能点，但无论将零势能点设置在哪里，两点间势能的差值是一定的。 在重新标记后的图上，从 s 点到 t 点的一条路径 s \to p_1 \to p_2 \to \cdots \to p_k \to t 的长度表达式为 (w(s,p_1)+h_s-h_{p_1})+(w(p_1,p_2)+h_{p_1}-h_{p_2})+ \dots +(w(p_k,t)+h_{p_k}-h_t)。

即 w(s,p_1)+w(p_1,p_2)+\cdots+w(p_k,t)+h_s-h_t。 无论我们从 s 到 t 走的是哪一条路径，h_s-h_t 的值是不变的，这正与势能的性质相吻合！

为了方便，下面我们就把 h_i 称为 i 点的势能。

上面的新图中 s \to t 的最短路的长度表达式由两部分组成，前面的边权和为原图中 s \to t 的最短路，后面则是两点间的势能差。因为两点间势能的差为定值，因此原图上 s \to t 的最短路与新图上 s \to t 的最短路相对应。

到这里我们的正确性证明已经解决了一半——我们证明了重新标注边权后图上的最短路径仍然是原来的最短路径。接下来我们需要证明新图中所有边的边权非负，因为在非负权图上，Dijkstra 能够保证得出正确的结果。

根据三角形不等式，图上任意一边 (u,v) 上两点满足：h_v \leq h_u + w(u,v)。这条边重新标记后的边权为 w'(u,v)=w(u,v)+h_u-h_v \ge 0。这样我们证明了新图上的边权均非负。

这样，我们就证明了 Johnson 全源最短路算法的正确性。

算法比较说明

注：SPFA 被单独拿出来进行讨论，不会与 Bellman-Ford 合并分析，因为其复杂度较为复杂。

• 单源最短路算法：Bellman-Ford，SPFA，Dijkstra。
• 多（全）源最短路算法：Floyd-Warshall，Johnson。

各项性能会在表格中列出

* : Aleph_Drawer 指出此处应补充说明，遂增加说明，由于内容属于拓展，放于剪切板中。

后记

Is SPFA dead?

后记偏个人对待最短路算法的看法，尤其是国内推 Dijkstra 且狂卡 SPFA 这件事。

关于 SPFA，她死了。

这里，我想为 SPFA 维权（并非激进分子，单纯觉得故意卡 SPFA 无意义）。SPFA 并不是没有救，可以看到的是很多 OIers 正在想方设法地去拯救她，出现了 SLF，LLL 这样的优化，虽然最终以失败告终，然而，目标是明确的。

个人并没有瞧不起 Dijkstra，她不仅在国内受欢迎，国外亦是如此。因为国外 OI 圈中并没有 SPFA 这个算法，所以他们用的都是 Bellman-Ford，这也就让他们有一种想法：除非必须，否则不用 Bellman-Ford。

然而，较为伟大的 SPFA 却可以类 O(m) 求出最短路，何尝不是一种好算法呢？

那么为啥 OI-wiki 上只记载了 n 轮 Dijkstra 的做法呢？原因很明显：它没有考虑负边权。所以只有在 Bellman-Ford 或 SPFA 的配合下 Dijkstra 才是完美的。

花儿没有小草的衬托终究是单调的。一个好的东西自然需要大家一起维护。Dijkstra 周围有 SPFA，这样才能使得最短路算法更加完美。

The knowledge I have got from this

至此，经典的最短路算法也就告一段落了。相信可以帮助大家获得一个更好的理解，这也是我的最终目标：可以让接触最短路算法较少的人一下豁然开朗。当然这也需要大量的努力和修改。

一切都是从没有到有，从一点到一片，从一个到许多。学习是一个累积的过程。我们学习 OI 的人中，我相信没有一个人可以真正坦言自己从来没有摸鱼过：电脑的诱惑太大了，即使有教练和家长看着，我们也有可能“趁人之危”，偷偷看看视频，玩玩游戏，唱唱歌等。

这段时光一定是快乐的，它也是不可或缺的一部分。尽管父母和教练都非常讨厌这种行为，然而我们如果可以把这个精力的 \dfrac{1}{4} 放在学习上，得到的结果最终定是不同的。

我不是在将一些别口的大道理，我只是想让读过这篇文章的人更加注重自己的学习，不要再摸鱼了。个人就是一个赤裸裸的例子，真的不想看到更多的受害者。 qwq

奇奇怪怪的东西（？）

更新历史

1. 2024.8.25 列举了 Floyd，Bellman-Ford，SPFA，Dijkstra 四个内容，但是缺少 Dijkstra 的严格证明。
2. 2024.8.26 详细给出了 Dijkstra 的严格证明，Johnson 全源最短路的算法理论，算法比较说明，后记。
3. 2024.8.27 给出 Johnson 全源最短路的代码实现和严格证明。
4. 2024.8.31 更新了“奇奇怪怪的东西（？）”。
5. 2024.11.05 提交一审。
6. 2024.11.10 一次打回。
7. 2024.11.10 增加“Johnson 全源最短路与最大流的相似之处”部分（感谢 Aleph_Drawer 提出的修改建议）。
8. 2024.11.10 删除私货。
9. 2024.11.10 提交二审（若通过则不继续更新“更新历史”板块以减轻管理员负担）