【算法】最短路算法

😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！💪💪💪

📗前言

---

咕咕咕，我是🕊白晨，最近一直在忙开学考试，托更了很久，果咩纳塞😱。

这次为大家分享的是图论中的最短路算法。考虑到最短路算法的复杂性以及本文新手向的教程，本次算法讲解列举了大量例子并且配上了大量动图。本篇文章所有的代码实现都是算法向的，以快速实现和效率为主，如果出现算法向的代码实在看不懂，可以参考白晨的工程向实现的代码，工程向代码链接：Graph。

---

📘最短路算法

---

最短路算法是指 一个图中，求某一个节点到其他节点的最短路径（最小权值路径）的算法。

最短路算法是图论中一类很重要的算法，也是算法题中经常会使用的一类算法。这种算法也可以和实际问题结合起来，比如 你要从西安到上海，要找到用时最短的一条路径，就需要这种算法。

🎗️Dijkstra

---

🍕朴素Dijkstra算法

---

🍬原题链接：Dijkstra求最短路 I

🪅算法思想：

朴素Dijkstra算法为单源最短路算法，适合稠密图，时间复杂度为 $O(n^2)$ （n为节点个数），对于边的存储结构为 邻接矩阵。

注意：Dijkstra算法必须要保证所有边的权值为正，否则算法的贪心策略证明失效。

• 具体做法

1. 初始化 dist 数组（初始化为无限大） 以及 $dist[1]=0$（一号节点到自己的距离为0）。
2. 遍历 dist 数组，选出其中距离最短的节点，选中此节点加入已确定最短距离的节点的集合S。
3. 根据上面确定节点的最短距离 更新 到达其他节点的最短距离（S集合中节点距离不可能再被更新）。
4. 重复2、3过程 N 次，N次迭代后，全部点的最短距离已经被确定。

以上的思想本质上来说是一种贪心策略，为什么能保证每次选中的距离1号节点最近的节点的路径就是最短路径呢？

Dijsktra迪杰斯特拉算法的证明（数学归纳法）和代码实现

证明见上面文章。

现在，我们来模拟一下Dijkstra算法的具体流程：

动画演示如下：

🪆代码实现：

// 朴素Dijkstra算法
#include <iostream>
#include <cstring>using namespace std;const int N = 510, INF = 0x3f3f3f3f;int n, m;int g[N][N]; // 邻接矩阵
int dist[N]; // 存储最短距离
bool book[N]; // 是否已确定最短路int Dijkstra()
{memset(dist, 0x3f, sizeof(dist));dist[1] = 0;// 循环n次for (int i = 0; i < n; ++i){// 选出距离1号节点距离最短的节点int u = -1;for (int j = 1; j <= n; ++j)if (!book[j] && (u == -1 || dist[u] > dist[j])) u = j;book[u] = true;// 更新边for (int i = 1; i <= n; ++i)if (!book[i] && dist[u] + g[u][i] < dist[i]) dist[i] = dist[u] + g[u][i];}if (dist[n] == INF) return -1;else return dist[n];
}int main()
{scanf("%d%d", &n, &m);memset(g, 0x3f, sizeof(g));while (m--){int a, b, w;scanf("%d%d%d", &a, &b, &w);g[a][b] = min(g[a][b], w); // 重边保留最小的边}printf("%d", Dijkstra());return 0;
}

---

🍔堆优化Dijkstra算法

---

🍬原题链接：Dijkstra求最短路 II

🪅算法思想：

堆优化Dijkstra算法为单源最短路算法，适用于稀疏图，时间复杂度为 $O(mlogn)$（m为边数，n为节点数），边的存储结构为邻接表。

相比于朴素版，本算法对于寻找路径最短的节点的过程进行了优化，改为了用小根堆堆存储最短路径，根据小根堆的特性，最短的路径就是堆顶元素，这样就省去了寻找最短路径的过程。

注意：Dijkstra算法必须要保证所有边的权值为正，否则算法的贪心策略证明失效。

• 具体做法
  1. 初始化 dist 数组，$dist[1]=0$，将{0,1}（距离为0，节点序号为1）入堆。
  2. 出堆顶元素，根据新确定最短路径以及节点下标更新其他路径（本次选用的存储结构为邻接表，所以直接遍历每个节点对应的链表即可）。
  3. 重复2过程，直到堆为空。

🪆代码实现：

// 堆优化Dijkstra算法
#include <iostream>
#include <queue>
#include <cstring>using namespace std;typedef pair<int, int> PII;const int N = 150010, INF = 0x3f3f3f3f;int n, m;// 这里只是我习惯的邻接表存储方式，也可以用结构体存储，只要能遍历一个节点的所有出边就可以
int g[N], e[N], ne[N], val[N], idx;// g为邻接表，e，ne，val为单链表，e存放节点序号，ne存放子节点下标，val存储权值
bool book[N]; // 此节点是否已经确定最短路径
int dist[N]; // 存储到1号节点的最短路径大小// 加边
void add(int a, int b, int w)
{e[idx] = b, val[idx] = w, ne[idx] = g[a], g[a] = idx++;
}int Dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> pq; // 小根堆pq.push({0, 1}); // 前面为距离，后面为节点序号while (pq.size()){auto t = pq.top();pq.pop();int st = t.first, node = t.second;// 由于题目有重边，所以可能会把一个节点更新多次，由于小根堆是距离小的先出，所以小边会先出确定最短路径，后面出的直接忽略即可if (book[node]) continue; book[node] = true;for (int i = g[node]; i != -1; i = ne[i]){int j = e[i];if (dist[node] + val[i] < dist[j]){dist[j] = dist[node] + val[i];pq.push({dist[j], j});}}}if (dist[n] == INF) return -1;else return dist[n];
}int main()
{scanf("%d%d", &n, &m);memset(g, -1, sizeof g);while (m--){int a, b, w;scanf("%d%d%d", &a, &b, &w);add(a, b, w);}printf("%d", Dijkstra());return 0;
}

---

---

🎞️Bellman-Ford

---

上图要求0点到其余点的最短距离，用Dijkstra算法可以吗？

可以看到Dijkstra这种贪心算法是完全失效了，第一次加入S集合的节点本来距离就应该确定了，但是有负权边时，会被继续更新。有负权边时，就应该把任务交给下面要介绍的Bellman-Ford算法了。

🍟有边数限制的最短路

---

🍬原题链接：有边数限制的最短路

🪅算法思想：

Bellman-Ford算法，带负权边单源最短路算法，时间复杂度为 $O(nm)$（顶点数*边数），本质上就是一个无脑遍历边的算法，所以边的存储不做要求，只要能遍历到全部边就可以，可以用结构体，也可以用邻接表等。

注意：Bellman-Ford算法可以求带负权边的最短路径，但是如果一个图中有负权回路，最短路径则不一定存在。

上图中，2、3、4号节点形成了一个环，如果要求1号节点到5号节点距离的最小值，可以走 1-2-3-4-3-5，总权值为3，也可以走 1-2-3-4-3-4-2-3-5，总权值为2。以此类推，可以无限走这个环，在没有路径边数的限制下，最小值为负无穷。

所以，Bellman-Ford算法可以用来求从 起始点 到 终点 的最多经过 k条边的最短距离，也可以用来判断负环（一般用SPFA算法判断，不用这个算法）。

• 具体做法：循环k次，每次遍历全部的边， 按照 dist[b] = min(dist[b], dist[a] + w) 更新b点到1号节点的距离即可。

与Dijkstra算法演示的例子相同：

对应的Bellman-Ford算法的动画演示如下：

🪆代码实现：

#include <iostream>
#include <cstring>using namespace std;const int N = 510, M = 10010, INF = 0x3f3f3f3f;struct Edge
{int a, b, w;
}edges[M];int n, m, k;
int dist[N], bkup[N]; // bkup是dist的备份，每次必须使用备份遍历，否则会出现更新顺序影响结果的情况void bellman_ford()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < k; ++i){// 每次必须用上一次更新完的值进行更新，如果直接用dist数组进行更新，会出现// 如果有3->1，2->3这两条边，k为1，如果先遍历到3->1这条边，dist[3]被更新，下面遍历2->3这条边，dist[2]也会被更新// 但是2节点到1节点必须要走两条边，不满足题意，所以每次必须用上一次更新完的值进行更新memcpy(bkup, dist, sizeof dist);for (int j = 0; j < m; ++j){auto& e = edges[j];dist[e.b] = min(dist[e.b], bkup[e.a] + e.w);}}
}int main()
{scanf("%d%d%d", &n, &m, &k);for (int i = 0; i < m; ++i){int a, b, w;scanf("%d%d%d", &a, &b, &w);edges[i] = {a, b, w};}bellman_ford();if (dist[n] > INF / 2) printf("impossible"); // 这里要注意，由于有负权边dist[a] = INF , dist[b] = INF, a->b w = -1时，dist[b] = INF - 1，小于INF，所以这里判断是否在一个区间else printf("%d", dist[n]);return 0;
}

---

---

🎟️SPFA

---

下面来看一个例子：

上面这个图，如果按照Bellman-Ford算法做，每次循环只有一次更新是有效的，其余全都是无效循环，大大浪费了时间。

我们发现，只有上一轮被更新过的节点，这一轮才会以该节点为出发点继续更新，所以能不能存储上一轮更新过的节点，这一轮直接遍历这些节点的出边，不就能大大减少无效的循环了吗？

🌭SPFA求最短路

---

🍬原题链接：SPFA求最短路

🪅算法思想：

SPFA算法，带负权单源最短路算法，时间复杂度一般为$O(m)$，最坏为$O(nm)$，本算法优化了Bellman-Ford算法每次遍历全部边的过程，本质上是 BFS ，边的存储结构为 邻接矩阵。

• 核心思路：只有 dist[a] 更新了， a->b 边才会被使用，否则不会使用a->b这条边，所以本算法存储更新过的最短路，很像Dijkstra堆优化版本。

• 具体做法：

  1. 初始化dist数组，$dist[1]=0$，将1号节点其入队。
  2. 广度优先搜索，出队节点元素，遍历每个节点的出边，更新，直到队列为空。

SPFA算法动画演示：

🪆代码实现：

// SPFA
#include <iostream>
#include <queue>
#include <cstring>using namespace std;const int N = 100010, INF = 0x3f3f3f3f;int n, m;
int g[N], e[N], ne[N], val[N], idx;
int dist[N];
bool book[N]; // 标记是否在队列中int SPFA()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);book[1] = true;while (q.size()){int u = q.front();q.pop();// 出队列以后记得更新状态book[u] = false;for (int i = g[u]; i != -1; i = ne[i]){int j = e[i];if (dist[u] + val[i] < dist[j]){dist[j] = dist[u] + val[i];// 防止重复添加if (!book[j]){q.push(j);book[j] = true;}}}}return dist[n];
}void add(int a, int b, int w)
{e[idx] = b, val[idx] = w, ne[idx] = g[a], g[a] = idx++;
}int main()
{scanf("%d%d", &n, &m);memset(g, -1, sizeof g); // g必须在add函数前更新for (int i = 0; i < m; ++i){int a, b ,w;scanf("%d%d%d", &a, &b, &w);add(a, b, w);}int ret = SPFA();if (ret == INF) puts("impossible");else printf("%d\n", ret);return 0;
}

---

🍿SPFA判断负环

---

🍬原题链接：spfa判断负环

🪅算法思想：

• 核心思想：设置一个cnt数组用来存储1号点到其他点路径中边的数量，使用SPFA算法进行更新，如果到一个节点到1号节点路径中边的数量 $cnt[i]>=n$，说明路径中出现环，如果出现环，一定是负环，因为正环不会 $dist[i]+环的路径<=dist[i]$ 也就不会被更新。

如何证明$cnt[i]>=n$就一定出现环呢？

反证法，如果$cnt[i]>=n$没有环，说明从1到 i 没有走过任何一个重复的节点，但是一共只有n个节点，当有n条边时，连接了n+1个节点，根据抽屉原理，必定有相同的节点，所以必定有环。

🪆代码实现：

// SPFA
#include <iostream>
#include <queue>
#include <cstring>using namespace std;const int N = 100010, INF = 0x3f3f3f3f;int n, m;
int g[N], e[N], ne[N], val[N], idx;
int dist[N], cnt[N];
bool book[N];bool SPFA()
{// 由于本题目只是用来判断负环，dist数组不表示最短距离，可以不需要初始化，这样更新的就只有负权边了queue<int> q;// 将全部节点入队，这里没有说是连通图，所以必须全部点先入队列for (int i = 1; i <= n; ++i){q.push(i);book[i] = true;}while (q.size()){int u = q.front();q.pop();// 出队列以后记得更新状态book[u] = false;for (int i = g[u]; i != -1; i = ne[i]){int j = e[i];if (dist[u] + val[i] < dist[j]){dist[j] = dist[u] + val[i];cnt[j] = cnt[u] + 1; // 路径更新if (cnt[j] >= n) return true;// 防止重复添加if (!book[j]){q.push(j);book[j] = true;}}}}return false;
}void add(int a, int b, int w)
{e[idx] = b, val[idx] = w, ne[idx] = g[a], g[a] = idx++;
}int main()
{scanf("%d%d", &n, &m);memset(g, -1, sizeof g); // g必须在add函数前更新for (int i = 0; i < m; ++i){int a, b ,w;scanf("%d%d%d", &a, &b, &w);add(a, b, w);}if (SPFA()) puts("Yes");else puts("No");return 0;
}

---

---

🎫Floyd

---

🧂Floyd求最短路

---

🍬原题链接：Floyd求最短路

🪅算法思想：

Floyd算法，多源最短路算法（一次可以求出所有节点到其他节点的最短路，有无负权边皆可使用），时间复杂度为$O(n^3)$，本质上是区间动态规划，核心代码只有四行，非常牛。边的存储结构：邻接矩阵。

• 状态：$f[i,j,k]$表示从$i$走到$j$的路径上除了$i$和$j$以外 只经过$1\sim k$号节点 的所有路径的最短距离。eg.$f[5,6,3]$表示 从$5$号节点走到$6$号节点 只经过 $1，2，3$ 这三个节点的最短距离

• 最初状态：$f[i,j,k]=\infty$

• 状态转移方程：$f[i,j,k]=min(f[i,j,k],f[i,k,k-1]+f[k,j,k-1])$，$i$节点到$j$节点只经过$1\sim k$号节点的最短距离等于 本身原值 和 $i$节点到$k$节点只经过$1\sim k-1$号节点最短距离和$k$节点到j节点只经过$1\sim k-1$号节点最短距离之和的最小值。

由于状态转移中，k层状态只需要用到k-1层状态，所以k这一维可以被优化掉。

🪆代码实现：

// Floyd算法
#include <iostream>
#include <cstring>using namespace std;const int N = 210, INF = 0x3f3f3f3f;int n, m, q;int g[N][N];void Floyd()
{// 在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}int main()
{scanf("%d%d%d", &n, &m, &q);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (i == j) g[i][j] = 0;else g[i][j] = INF;while (m--){int a, b, w;scanf("%d%d%d", &a, &b, &w);g[a][b] = min(g[a][b], w);}Floyd();while (q--){int a, b;scanf("%d%d", &a, &b);if (g[a][b] > INF / 2) puts("impossible");else printf("%d\n", g[a][b]);}return 0;
}

---

---

📙后记

---

最后总结一下上面所有算法：

• 单源最短路算法
  • 朴素Dijkstra：贪心算法，必须保证无负权边，适合稠密图，时间复杂度为 $O(n^2)$ （n为节点个数），对于边的存储结构为 邻接矩阵。
  • 堆优化Dijkstra：贪心算法，必须保证无负权边，适用于稀疏图，时间复杂度为 $O(mlogn)$（m为边数，n为节点数），边的存储结构为邻接表。
  • Bellman-Ford：循环遍历，时间复杂度为 $O(nm)$（顶点数*边数），所以边的存储不做要求，只要能遍历到全部边就可以，可以用结构体，也可以用邻接表等。
  • SPFA：BFS，时间复杂度一般为$O(m)$，最坏为$O(nm)$，边的存储结构为 邻接矩阵。
• 多元最短路算法
  • Floyd：动态规划，时间复杂度为$O(n^3)$，边的存储结构为邻接矩阵。

---

如果解析有不对之处还请指正，我会尽快修改，多谢大家的包容。

如果大家喜欢这个系列，还请大家多多支持啦😋！

如果这篇文章有帮到你，还请给我一个大拇指 👍和小星星 ⭐️支持一下白晨吧！喜欢白晨【算法】系列的话，不如关注👀白晨，以便看到最新更新哟！！！

我是不太能熬夜的白晨，我们下篇文章见。