【知识点】图论续篇 - 最短路算法合集

我不会跟大家说我两个月前就写好了，只是今天才发出来。

本文概述

最短路算法，见名知意，就是用于求出图中从某个顶点到另一个顶点最短距离的算法。最短路算法的应用极其广泛。本文将会以求解最短路为中心，围绕着展开叙述一些常见的最短路算法的原理和应用。

根据最短路算法，我们大致地可以将算法分为两大类：

1. 单源最短路径 Single Source Shortest Path：用于快速计算从某一个特定顶点出发到达任意一个点的距离。
2. 多源最短路径 Multiple Source Shortest Path：用于快速计算任意两点之间的最短路径。

本文将会介绍的算法和各算法的特点如下：

1. 深度优先搜索 Depth First Search：单源最短路径算法，可以求解从任意一点开始到另一点的最短路径，但该算法极其耗时。
2. 广度优先搜索 Breadth First Search：单源最短路径算法，仅用于求解无权图。
3. 迪克斯特拉算法 Dijkstra Algorithm：单源最短路径算法，是广度优先搜索算法的加强版。Dijkstra 算法不能处理带有负权边的情况，更不能处理带有负权回路的图。
4. 贝尔曼福特算法 Bellman-Ford Algorithm：单源最短路径算法，可以用于处理又负权边的情况。对其进行队列优化后就变成了我们熟知的 SPFA 算法。
5. 弗洛伊德算法 Floyd Algorithm：多源最短路径算法，基于动态规划思想，能够一次性求出图中任意两点之间的最短路径，但该算法的时间复杂度非常高，达到惊人的 $O(N^3)$。弗洛伊德算法能处理带有负权边的情况，但不能处理带有负权回路的图。

为了方便阅读，本文提供的所有代码均会使用 vector 实现的邻接表来存图。

场景引入

在下图中，有 $7$ 条不同的边，每一条路径上方都标记了一个数值 $T_i$，代表通过该条路径所需要的时间。Macw 想知道从 $1$ 号顶点到 $5$​ 号顶点所需要花费的最短时间。

不难看出，Macw 所需要花费的最短时间是 $14$ 分钟，一条可行的方案是从 $1$ 号顶点出发，途径 $2$，$3$ 号顶点到达顶点 $5$。虽然人脑可以很快的看出来，但是在庞大的数据量下，人的脑力就显得极其渺小。那对于计算机来说，我们如何能找到一条从 $1$ 号节点到 $5$ 号节点的路径呢？不妨让计算机暴力枚举出所有的可行路径和每条路径分别的耗时，取最小的那一条路径就可以了。深度优先搜索算法是一个选择。

深度优先搜索 Depth First Search

如上图所示，从 $1$ 号节点到 $5$ 号节点共有四条路径，每条路径和其分别耗时如下：

1. $1\to 2\to 5$，耗时 $2+16=18$ 分钟。
2. $1\to 2\to 3\to 5$，耗时 $2+7+5=14$ 分钟。
3. $1\to 4\to 5$，耗时 $6+12=18$ 分钟。
4. $1\to 4\to 3\to 5$，耗时 $6+6+5=17$ 分钟。

其中第二个方案是最优解，耗时 $14$ 分钟。因此，一个可行的算法方案是使用深度优先搜索暴力枚举出所有可行的路径并记录最小值即可，其代码实现如下：

// ans 用于记录答案，一开始把答案设置为无穷大。
int ans = 0x7f7f7f7f; 
// 记录一个点是否被访问过，防止出现循环。
int vis[105];
struct Edge{int to;int weight;
}; vector<Edge> G[105];// 表示到 node 节点的耗时为 steps。
void dfs(int node, int steps){if (steps >= ans) // 最优性剪枝。// 如果走到目标答案，就更新结果并返回。if (node == terminal){ans = min(ans, steps);return ;}for (Edge next : G[node]){// 遍历从 node 开始所有的边。if (vis[next.to]) continue ;  // 被访问过了，就跳过。vis[next.to] = 1;  // 将节点标记为已访问的状态。dfs(next.to, steps + next.weight);  // 继续递归。vis[next.to] = 0;  // 将节点标记为未访问的状态。}return ;
}

深度优先嗖嗖算法虽然很有效，但是该算法的运行效率太低下了，只适用于数据量较小的情况。假设图是一个二叉树树形结构，那么在最坏的情况下，这个算法的时间复杂度将会达到 $O(2^N)$。当每个顶点的度越多，深度优先搜索算法的时间复杂度就高。因此，在一般情况下，我们不会使用深度优先搜索。

设想在二维 $N\times M$ 地图问题的情况下，我们怎么找到从入口到出口的最佳路径？一般情况下，我们会使用广度优先搜索的算法。广度优先搜索算法的复杂度远远低于深度优先搜索。

广度优先搜索算法 Breadth First Search

在一个无权图中（或图中所有边的权值均为 $1$）的情况下，我们会使用广度优先搜索算法来实现。广度优先搜索算法的代码也很简洁：

struct node{int pos;int steps;
}; queue<node> que;
struct Edge{int to;int weight;
}; vector<Edge> G[105];
// 记录一个点是否被访问过，防止出现循环。
int vis[105];void bfs(int start){que.push(start)  // 将起点加入队列。while(!que.empty()){node t = que.front();que.pop();// 如果走到目标答案，就输出答案并终止循环。if (t.pos == terminal){cout << t.steps << endl;return ;}// 遍历从 t 开始所有的边。for (Edge next : G[t]){// 如果被访问过了，就略过。if (vis[next.to]) continue;vis[next.to] = 1;// 将新的节点加入到队列之中。que.push((node){next.to, t.steps + next.weight});}}return ;
}

我们已经知道，在一般的地图问题中广度优先搜索的效率非常高。那我们是否可以加以改进广度优先算法，让它适配带权图呢？答案是可以的，经过改编后的算法就是大名鼎鼎的 Dijkstra 算法。

迪克斯特拉算法 Dijkstra Algorithm

Dijkstra 算法是一种用于寻找图中从单一源节点到其他所有节点的最短路径的算法（即单源最短路径算法）。它适用于所有边权重为非负值的图。这个算法最早是被荷兰计算机科学家 艾兹赫尔·戴克斯特拉 (Edsger W. Dijkstra) 发明并提出的，因此用他的名字来命名该最短路算法。

Dijkstra 算法的基本思想是逐步扩展最短路径，直到覆盖所有节点。依旧以「场景引入」章节的图来举例子，虽然我们没有办法一下子立刻求解出从 $1$ 号节点到 $5$ 号节点的最短路径，但是如果我们能求出从 $1$ 号节点到 $5$ 号节点所有的前驱节点的最短路径，那么我们就可以立刻计算出从起点到 $5$ 号节点最短路。

如上图所示，$5$ 号节点有三个前驱节点，分别是节点 V = { 2 , 3 , 4 } V = \{2, 3, 4\} V={2,3,4}，走到这三个节点的最短距离分别为两分钟、九分钟和六分钟。通过遍历这些前驱节点，我们就可以求出从起点到终点的最短路。显然，对于图中所有的节点，我们都需要按照一定的顺序依次对它们进行相同的操作。这样子，我们就可以求解出从起点开始到图中任意一个点的最短距离了。

Dijkstra 算法具体的实现流程如下：

1. 初始化：
   • 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 $0$，其他所有节点的距离为 $+\infty$​。
   • 将所有节点标记为未访问。
   • 使用一个优先队列来存储节点及到某一个节点当前所计算出的最短距离。
2. 选择节点：
   • 从未访问的节点中选择当前距离最小的节点作为当前节点。
   • PS：如没有特殊情况，一开始这个节点应该是求解最短路问题的起点（起点与自己的距离应该是 $0$，正如初始化步骤中所提及的）。
3. 更新节点：
   • 对于当前节点的每个邻居节点，计算从当前节点到该邻居节点的距离。
   • 如果这个距离小于已知的到该邻居节点的距离，则更新该邻居节点的距离。
   • 距离更新: 对于每个邻居节点，计算从起点到该邻居节点的距离，如果该距离小于已知的最短距离，则更新最短距离。
4. 标记已访问：
   • 将当前节点标记为已访问，表示已经处理完了该节点。
   • PS：当节点被标记完已访问后，从起点到该节点的最短距离就已经被正式确定下来了，在后续的计算过程中该节点的距离将不会再被更新。标记节点已访问可以在「选择节点」步骤完成后时就进行。换句话说，第三步和第四步的顺序并不重要。
5. 重复循环：
   • 重复上述提到的第 2-4 步，直到所有的点都被标记为已访问。

以下是使用 Dijkstra 算法对例题的模拟过程：

首先初始化距离数组，将源点的距离设置为 $0$，将除源点以外的所有点的距离设置为 $+\infty$。正无穷大表示到达该点的最短距离还未知。

从未访问的节点中选择当前距离最小的节点作为当前节点。在一开始，距离最小的节点就是源点本身。如下图，浅绿色表示当前选中的节点，黄色表示该节点的邻居节点。接下来就开始更新两个邻居节点距源点的最近距离。从 $1$ 号点到 $2$ 号点的最短距离为 $2$，而 $2$ 号节点当前所记录的最短距离是 $+\infty$，比较发现 $2<+\infty$，因此将 $2$ 号点的距离从原本的正无穷更新为 $2$。节点 $4$ 也是如此，从起点到该节点的最短路径将由原本的正无穷更新为 $6$。

此时，$1$ 号节点已经处理完成了，我们将该节点标记为已访问（图中用深绿色表示）。接下来，我们从未访问的节点当中选择一个距离最小的节点作为当前节点。如下图，未访问的节点有 V = { 2 , 3 , 4 , 5 } V = \{2, 3, 4, 5\} V={2,3,4,5}，其当前的距离分别为 D i s = { 2 , + ∞ , 6 , + ∞ } Dis = \{2, +\infty, 6, +\infty\} Dis={2,+∞,6,+∞}，因此我们选择 $2$ 号节点作为新的当前节点，因为该节点是所有未访问节点当中距离源点距离最小的那个节点。

从 $2$ 号节点开始，更新该节点的所有邻居节点。对于 $5$ 号节点，原本的距离是 $+\infty$，但从源点出发，经过 $2$ 号节点的距离为 $2+16=18$，显然这个距离比原本的正无穷大更优，因此更新该节点的最短距离为 $18$。对于 $3$ 号节点也是如此，从源点出发经过 $2$ 号节点的最短距离是 $2+7=9$，因此将 $3$ 号节点的距离更新为 $9$。

将 $2$ 号节点标记为已访问。接下来再从未访问的节点中选择一个距离最近的节点，现在未访问的节点有 V = { 3 , 4 , 5 } V = \{3, 4, 5\} V={3,4,5}，其中 $4$ 号节点的距离最短，因此选择 $4$ 号节点作为当前节点。从 $4$ 号节点出发可以到达的节点只有 $3$ 号节点，如果从源点出发经过 $4$ 号节点再到 $3$ 号节点的距离为 $6+6=12$，这显然比当前 $3$ 号的距离更大，因此这不是一个更优的解，本轮将不再更新 $3$ 号节点的最短距离。

将 $4$ 号节点标记为已访问。现在再从未访问的节点中选择一个距离最小的节点作为当前节点，因此我们将选择 $3$ 号节点作为当前节点。我们发现从源点出发经过 $3$ 号节点到 $5$ 号节点的距离为 $9+5=14$，这比 $5$ 号节点当前记录的 $18$ 更优，因此更新 $5$ 号节点的最短距离。

将 $3$ 号节点标记为已访问。

选择 $5$ 号节点作为当前节点。由于 $5$ 号节点没有任何的后继节点，因此循环结束。将 $5$ 号节点标记为已访问。

至此，所有的节点都标记为已访问，Dijkstra 算法结束。此时距离数组记录的值就是从源点出发到各个点的最短距离。

在下方代码中，为了快速的找到当前距离最小的节点，我们将会使用 C++ 自带的优先队列 (Priority Queue) 数据结构来实现。

完整的 Dijkstra 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1）：

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define int long long
using namespace std;const int N = 1e6;int n, m, s;
int u, v, w;
struct Edge{int to;int weight;
}; vector<Edge> G[N];
struct node{int position;int distance;// 优先队列优化，按照 distance 从小到大进行排序。bool friend operator < (node a, node b){return  a.distance > b.distance;}
};
// dis 数组用于记录从起点开始到任意一个点的最短路。
// vis 数组用于记录一个节点是否已经被访问过了。
int dis[N], vis[N];void dijkstra(int origin){// 初始化：将所有非起点外的点都初始化为正无穷大。for (int i=1; i<=n; i++) dis[i] = 2147483647;dis[origin] = 0;// 优先队列初始化：一开始将起点加入队列。priority_queue<node> que;que.push((node){origin, 0});while(que.size()){node t = que.top();que.pop();// 如果节点被访问过了，则略过。否则标记该节点为已访。if (vis[t.position]) continue;vis[t.position] = 1;  // 也可以写在最后。// 遍历所有的邻居节点。for (Edge next : G[t.position]) {int to = next.to;int w = next.weight;// 如果存在一条更优秀的路径，则更新最短路。if (dis[to] > w + dis[t.position]){dis[to] = w + dis[t.position];// 将节点加入到优先队列之中。que.push((node){to, w + dis[t.position]});}}}return ;
}signed main(){// 输入输出优化。ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);// 读入题目数据并建图。cin >> n >> m >> s;for (int i=1; i<=m; i++){cin >> u >> v >> w;G[u].push_back((Edge){v, w});}// 运行最短路算法。dijkstra(s);// 输出结果，如果 dis 还是正无穷大，则证明改节点无法到达。for (int i=1; i<=n; i++) cout << (dis[i] == 2147483647 ? -1 : dis[i]) << " ";return 0;
}

由于该算法是基于优先队列实现的，优先队列求出最小值的复杂度为 $O(lo{g}_2(V))$（使用了二叉堆优化），因此 Dijkstra 的时间复杂度约为 $O((V+E)\times lo{g}_{2}V)$，其中 $V$ 代表图中顶点的数量，$E$ 代表图中边的数量。相比之下，Dijkstra 算法的运行效率非常优越。该算法也是在求解最短路问题中应用最广泛的算法之一。

贝尔曼福特算法 Bellman-Ford Algorithm

Bellman-Ford 算法也是一种用于求解单源最短路径问题的算法，特别适用于含有负权边的图。与 Dijkstra 算法不同，Bellman-Ford 算法能够检测到负权重环路的存在。

Bellman-Ford 的算法思想是通过 松弛操作 (Relaxation) 逐步找到从源点到所有其他顶点的最短路径。对一条边进行松弛操作指的是检查一条边/图上的路径是否能提供更短的路径。如果可以，那么就更新答案。

该算法会重复对图中的所有边进行松弛操作，总共执行 $|V|-1$ 次，其中 $|V|$ 是图中顶点的数量。

Bellman-Ford 算法具体的实现流程如下：

1. 初始化：
   • 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 $0$，其他所有节点的距离为 $+\infty$​。
2. 松弛操作：
   • 对于每一条边 $(u,v)$，和这条边的权重 $w(u,v)$，如果可以使得 $di{s}_u+w(u,v)<di{s}_v$，则将 $di{s}_v$ 更新为 $di{s}_u+w(u,v)$。其中，$di{s}_i$ 表示编号为 $i$ 节点的距离。
   • 重复上述步骤 $|V|-1$ 次。
3. 检测是否存在负环：
   • 再次对所有边执行松弛操作。如果发现某条边 $(u,v)$ 仍能使 $di{s}_u+w(u,v)<di{s}_v$ 成立，则说明图中存在负权重环路。
   • 换句话说，如果一个图不存在负环，则这张图的边在经历最多 $|V|-1$ 次松弛操作后将不能再进行松弛了。

以下是使用 Bellman-Ford 算法对例题的模拟过程：

首先初始化距离数组，将源点的距离设置为 $0$，将除源点以外的所有点的距离设置为 $+\infty$。正无穷大表示到达该点的最短距离还未知。

选择一条边，对该边尝试进行一次松弛操作。如下图（红色的边表示当前选中的边），通过这一条边可以将从源点到 $2$ 号点的距离从正无穷大缩短至 $2$，因此更新新的距离。

以次类推，依次遍历并尝试松弛所有的边。当每一条边经历 $|V|-1$ 次松弛操作后，算法结束。此时距离数组记录的值就是从源点出发到各个点的最短距离。

完整的 Bellman-Ford 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1，由于标准版的 Bellman-Ford 算法运行效率低下，因此不保证可以通过所有的测试点）：

#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;const int N = 1e6;int n, m, s, dis[N];
struct Edge{int from, to;int weight;
}; vector<Edge> edges; void bellman_ford(int origin){// 初始化：将所有非起点外的点都初始化为正无穷大。for (int i=1; i<=n; i++) dis[i] = 2147483647;dis[origin] = 0;// 由于图中保证不存在负环，则循环 n-1 遍即可。for (int i=1; i<=n-1; i++){for (Edge edge : edges){// 进行松弛操作。dis[edge.to] = min(dis[edge.to], dis[edge.from] + edge.weight);}}return ;
}signed main(){// 输入输出优化。ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);// 读入题目数据并建图。cin >> n >> m >> s;for (int i=1, u, v, w; i<=m; i++){cin >> u >> v >> w;edges.push_back((Edge){u, v, w});}// 运行最短路算法。bellman_ford(s);// 输出结果，如果 dis 还是正无穷大，则证明改节点无法到达。for (int i=1; i<=n; i++) cout << (dis[i] == 2147483647 ? -1 : dis[i]) << " ";return 0;
}

使用 Bellman-Ford 算法判断负环的方法如下（对应例题：ACGO - A551.单源最短路径2）：

// 其他地方都不需要作改动，只改动核心松弛部分就可以了。
// 在进行第n轮松弛的时候，如果某一条边还可以松弛那么就说明这个图中存在负环。for (int i=1; i<=n; i++){for (Edge edge : edges){// 进行松弛操作。if (dis[edge.from] + edge.weight < dis[edge.to]){// 如果在第 n 次还是可以对其进行松弛操作，那么就证明有负环。if (i == n){cout << "no solution" << endl;exit(0);}dis[edge.to] = dis[edge.from] + edge.weight;}}
}

因为 Bellman-Ford 算法要对每条边进行 $|V|-1$ 次松弛操作，并且还需要判断一次是否存在负环，因此该算法的时间复杂度为 $O(V\times E)$，其中 $V$ 是顶点数，$E$ 是边数。Bellman-Ford 的时间复杂度相对来说比较高，因此在没有负环的时候仍然推荐使用 Dijkstra 最短路算法作为首选方案。

SPFA 算法 Shortest Path Faster Algorithm

SPFA (Shortest Path Faster Algorithm) 算法是 Bellman-Ford 算法的改进版本，专门用于加速单源最短路径的计算。该算法通过队列机制减少了不必要的松弛操作，从而提高了代码的运行效率。SPFA算法在实践中表现出优异的性能，特别是在稀疏图中。

SPFA 算法利用一个队列来存储需要松弛的顶点，并且每个顶点在队列中最多出现一次。通过这种机制，SPFA 算法避免了对所有边进行多余的松弛操作，从而提高了效率。

但 SPFA 算法也有缺陷，在一些特殊的情况下，可能会出现卡死的情况（有一句古话：关于 SPFA，它死了）。在最坏的情况下，SPFA 的复杂度高达 $O(V\times E)$（就是普通 Bellman-Ford）算法的运行效率。但该算法在大多数情况下表现优异，通常情况该算法的平均时间复杂度在 $O(V+E)$ 附近，其中 $V$ 是图中顶点的数量，$E$ 是图中边的数量。

SPFA 算法具体的实现流程如下：

1. 初始化：

   • 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 $0$，其他所有节点的距离为 $+\infty$​。

   • 初始化一个队列（不需要是优先队列，普通队列即可）。将源点加入到队列之中。

   • 初始化一个数组用来记录某个顶点是否在队列之中。在程序开始时，源点应该被标记为已经入队。

2. 松弛操作：

   • 对于每一条边 $(u,v)$，和这条边的权重 $w(u,v)$，如果可以使得 $di{s}_u+w(u,v)<di{s}_v$，则将 $di{s}_v$ 更新为 $di{s}_u+w(u,v)$。其中，$di{s}_i$ 表示编号为 $i$ 节点的距离。
   • 如果成功进行了松弛操作，且顶点 $v$ 不在队列之中，那么将顶点 $v$ 加入到队列之中。

3. 重复执行：

   • 重复第二部的操作，直到队列为空。
   • PS：如果某个点加入了队列 $|V|$ 次，则说明该图存在负环，应该立结束程序。

以下是使用 SPFA 算法对例题的模拟过程：

首先初始化距离数组，将源点的距离设置为 $0$，将除源点以外的所有点的距离设置为 $+\infty$。正无穷大表示到达该点的最短距离还未知。同时，将源点加入到队列之中，并将源点标记为已加入队列。

选择队首元素（在当前情况就是 $1$ 号节点），松弛与 $1$ 号节点相邻的两条边。从 $1$ 号节点出发，到 $2$ 号节点和 $4$ 号节点的距离都比正无穷大要小，因此更新这两个节点的距离。与此同时，由于 $2$ 号节点和 $4$ 号节都不在队列中，因此将这两个节点加入到队列。

弹出位于队首的 $1$ 号元素，选择位于队首的 $2$ 号元素，松弛与 $2$ 号节点相邻的两条边。从 $2$ 号节点出发，到 $3$ 号节点和 $5$ 号节点的距离都比正无穷大要小，因此更新这两个节点的距离。与此同时，由于 $3$ 号节点和 $5$ 号节都不在队列中，因此将这两个节点加入到队列。

弹出位于队首的 $2$ 号元素，选择位于队首的 $4$ 号元素，松弛与 $4$ 号节点相邻的两条边。从 $4$ 号节点出发，到 $3$ 号节点和 $5$ 号节点的距离都比原本要远，因此不更新任何节点，也不将任何节点加入到队列当中。

弹出位于队首的 $4$ 号元素，选择位于队首的 $3$ 号元素，松弛与 $3$ 号节点相邻的两条边。从 $3$ 号节点出发，到 $5$ 号节点的距离为 $9+5=14$，比原本的 $18$ 要更优，因此更新 $5$ 号节点。但由于 $5$ 号节点已经被加入到了队列之中，因此不再重复加入。

弹出位于队首的 $3$ 号元素，选择位于队首的 $5$ 号元素，由于该节点不存在任何的后继节点，因此不做任何操作，直接将 $5$ 号节点弹出队列。至此，队列为空，SPFA 算法结束。

完整的 SPFA 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1，由于标准版的 SPFA 算法最坏的情况会被卡死，因此不保证可以通过所有的测试点）：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define int long long
using namespace std;const int N = 1e6;int n, m, s, dis[N], inque[N];
struct Edge{int to;int weight;
}; vector<Edge> G[N];void SPFA(int origin){// 初始化：将所有非起点外的点都初始化为正无穷大。for (int i=1; i<=n; i++) dis[i] = 2147483647;dis[origin] = 0;// 将源点加入到队列之中。queue<int> que;que.push(origin);inque[origin] = 1;// 循环直至队列不为空。while(!que.empty()){int t = que.front();inque[t] = 0;que.pop();for (Edge next : G[t]){// 进行松弛操作。if (dis[t] + next.weight < dis[next.to]){dis[next.to] = dis[t] + next.weight;// 如果不在队列之中，就将点加入队列。if (!inque[next.to]){que.push(next.to);inque[next.to] = 1;}}}}return ;
}signed main(){// 输入输出优化。ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);// 读入题目数据并建图。cin >> n >> m >> s;for (int i=1, u, v, w; i<=m; i++){cin >> u >> v >> w;G[u].push_back((Edge){v, w});}// 运行最短路算法。SPFA(s);// 输出结果，如果 dis 还是正无穷大，则证明改节点无法到达。for (int i=1; i<=n; i++) cout << (dis[i] == 2147483647 ? -1 : dis[i]) << " ";return 0;
}

使用该算法判断负环，只需要判断是否存在一个节点被加入了超过 $|V|-1$​ 次即可。完整的 SPFA 判断是否存在负环的代码如下（对应例题：洛谷 - P3385 【模板】负环）：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define int long long
using namespace std;const int N = 1e6;int T, n, m, s;
int cnt[N], dis[N], inque[N];
struct Edge{int to;int weight;
}; vector<Edge> G[N];void SPFA(int origin){// 初始化：将所有非起点外的点都初始化为正无穷大。for (int i=1; i<=n; i++) dis[i] = 2147483647;dis[origin] = 0;// 将源点加入到队列之中。queue<int> que;que.push(origin);inque[origin] = 1;// 循环直至队列不为空。while(!que.empty()){int t = que.front();cnt[t] += 1;inque[t] = 0;que.pop();if (cnt[t] >= n){cout << "YES" << endl;return ;}for (Edge next : G[t]){// 进行松弛操作。if (dis[t] + next.weight < dis[next.to]){dis[next.to] = dis[t] + next.weight;// 如果不在队列之中，就将点加入队列。if (!inque[next.to]){que.push(next.to);inque[next.to] = 1;}}}}cout << "NO" << endl;return ;
}void solve(){// 读入题目数据并建图。cin >> n >> m;for (int i=1; i<=n; i++){G[i].clear();inque[i] = 0;cnt[i] = 0;}for (int i=1, u, v, w; i<=m; i++){cin >> u >> v >> w;G[u].push_back((Edge){v, w});if (w >= 0) G[v].push_back((Edge){u, w});}SPFA(1);  // 判断是否存在负环。
}signed main(){// 输入输出优化。ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin >> T; while(T--) solve();return 0;
}

弗洛伊德算法 Floyd Algorithm

Floyd 算法运用了动态规划的思想，该算法用于求解所有顶点对之间的最短路径问题。Floyd 算法适用于带权有向图，可以处理负权重边，但不能处理图中含有负权重环的情况。

Floyd l算法通过三重循环迭代地更新最短路径。设定一个二维矩阵 $Dis$，其中 $Di{s}_{i,j}$ 表示从顶点 $i$ 到顶点 $j$ 的最短路径权重。初始时，将直接相连的顶点的距离设置为边的权重，没有直接连接的顶点距离设为无穷大，顶点到自身的距离设为 $0$。

该算法的核心思想是，检查每一对顶点 $(i,j)$ 是否可以通过另一个顶点 $k$（作为中转节点） 使得从 $i$ 节点到 $j$ 节点的路径更优。如果通过 $k$ 可以使路径更短，则更新 $Di{s}_{i,j}$。

因此可以得到状态转移方程：$Di{s}_{i,j}=\min (Di{s}_{i,k}+Di{s}_{k,j},Di{s}_{i,j})$。

综上所述，Floyd 的代码如下（对应例题：洛谷 - B3647 【模板】Floyd）：

#include <iostream>
#define int long long
using namespace std;int n, m, dis[105][105];void init(){for (int i=1; i<=n; i++){for (int j=1; j<=n; j++){dis[i][j] = 2147483647;}dis[i][i] = 0;}return ;
}signed main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin >> n >> m;init();  // 初始化。// 读入数据与建图。for (int i=1, u, v, w; i<=m; i++){cin >> u >> v >> w;dis[u][v] = dis[v][u] = min(dis[u][v], w);}// 进行动态规划。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++){cout << dis[i][j] << " ";}cout << endl;}return 0;
}

Floyd 算法的时间复杂度在 $O(N^3)$，其中 $N$ 表示图中顶点的数量。因此该算法的执行效率是极其低的，在没有特殊情况下，尽量避免使用该算法。但如果遇到多源最短路径的题目，Floyd 算法还是首选方案。

Dijkstra 算法和 SPFA 算法的主要区别

1. 处理负权边：
   • SPFA：可以处理负权边，并且在某些情况下表现出色。SPFA还可以检测负权环。
   • Dijkstra：无法处理负权边，因为 Dijkstra 算法假设已经找到的最短路径，且不会被后续路径更新。
2. 队列机制：
   • SPFA：使用一个队列来存储需要处理的顶点。顶点可能多次进入队列，但每次只有在更短路径被发现时才重新入队。
   • Dijkstra：使用优先队列（通常是最小堆）来存储顶点，以确保每次处理的顶点是当前最短路径确定的顶点。
3. 时间复杂度：
   • SPFA：在实际应用中通常表现良好，平均时间复杂度为 $O(V+E)$，但最坏情况下为 $O(V\times E)$。
   • Dijkstra：使用最小堆实现时，时间复杂度为 $O((V+E)\times lo{g}_{2}V)$。

本期讲解了常见的几种求解最短路问题的算法，共计 8409 字。谢谢阅读。