文章目录
一、拓扑排序二、求最短路1.Dijkstra算法 ★
1.1 朴素Dijkstra算法 O(n^2^)1.2 堆优化的Dijkstra算法 O(mlogn) ★ 2.Bellman-Ford算法3.SPFA算法 ★
3.1 SPFA求最短路3.2 SPFA判断负环 一、拓扑排序
题目描述：
输入
4 31 22 43 4
输出
1 3 2 4
C++ 代码如下
#include #include #include #include using namespace std;const int N = 1e5 + 10;int n, m;int h[N], e[N], ne[N], idx; // 邻接表queue q;int d[N]; // 存放入度 int top[N]; // 记录拓扑序列int cnt = 0;void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}bool topsort(){ int t; for (int i = 1; i <= n; i++){ if(d[i] == 0) q.push(i); // 将入度为0的点加入队列 } while(q.size()){ t = q.front(); top[cnt++] = t; q.pop(); // 遍历t的出边j for(int i = h[t]; i != -1; i = ne[i]){ int j = e[i]; d[j] --; //j的入度-1 if(d[j] == 0) q.push(j); } } // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。 return cnt == n; // if(cnt < n) return 0; // else return 1;}int main(){ cin >> n >> m; memset(h, -1, sizeof h); for(int i = 0; i < m; i ++){ int a, b; cin >> a >> b; add(a, b); d[b] ++; // 插入边时，更新入度 } if(topsort()){ for(int i = 0; i < n; i ++){ cout << top[i] << " "; } } else cout << -1; return 0;}
二、求最短路 1.Dijkstra算法 ★
题目描述：
1.1 朴素Dijkstra算法 O(n2)
#include #include #include #include using namespace std;const int N = 510;int g[N][N]; // N <= 500 稠密图 : 邻接矩阵int dist[N]; // 记录每个点到起点的 距离bool st[N]; // 记录每个点到起点的最短距离 是否确定！// 集合s ： stint n, m;int dijkstra() { // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1 memset(dist, 0x3f, sizeof dist); //初始化距离为 ∞ dist[1] = 0; //第一个点到自身的距离为0 // 迭代n次，每次可以确定一个点到起点的最短距离 for (int i = 0; i < n; ++i) { int t = -1; // 临时变量 for(int j = 1; j <= n; j++){ //如果j点未确定最短距离 且 j到起点的距离 < t到起点的距离，则更新 if(!st[j] && (t == -1 || dist[j] < dist[t])){ t = j; // 更新各点到起点的最小距离(find min distance) } } // 此时t点到起点距离最小，则把t加入集合s st[t] = true; // 用t点更新最小距离 1 -> t -> j 和 1 -> j for(int j = 1; j <= n; j++){ dist[j] = min(dist[j], dist[t] + g[t][j]); // d[j] < d[t] + w } } if(dist[n] == 0x3f3f3f3f) return -1; // 起点到不了n点 返回-1 return dist[n];}int main(){ cin >> n >> m; memset(g, 0x3f, sizeof g); // 初始化图 每个点到起点的距离为 ∞ while (m -- ){ int a, b, c; cin >> a >> b >> c; g[a][b] = min(g[a][b], c); //g 为领接矩阵 最小权值 } cout << dijkstra() <
【注】
int t = -1; t 的作用？
一开始t的赋值是-1
如果t没有被更新，
那么要更新一下t
0x3f和0x3f3f3f3f 的区别？
memset 按字节赋值，所以memset 0x3f 就等价与赋值为0x3f3f3f3f
1.2 堆优化的Dijkstra算法 O(mlogn) ★
代码如下
#include #include #include #include using namespace std;const int N = 1e6 + 10;typedef pair PII; int h[N], e[N], w[N], ne[N], idx; // N ~ 1e5 用邻接表int dist[N]; // 记录每个点到起点的 距离bool st[N]; // 记录每个点到起点的最短距离 是否确定！// 集合s ： stint n, m;void add(int a, int b, int c) { // 添加一条边a->b，边权为c e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;}int dijkstra() { // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1 memset(dist, 0x3f, sizeof dist); //初始化距离为 ∞ dist[1] = 0; //第一个点到自身的距离为0 priority_queue, greater> heap; // 定义 小根堆 heap.push({0, 1}); // first 为距离, second 为结点编号 while(heap.size()){ auto t = heap.top(); // t = 堆顶(当前最小的点) heap.pop(); int ver = t.second; int distance = t.first; // min distance if(st[ver]) continue; // 如果结点被访问过，则跳过(重边) st[ver] = true; for(int i = h[ver]; i != -1; i = ne[i]){ int j = e[i]; if(dist[j] > distance + w[i]){ // 若1 -> j 大于 1 -> t -> j dist[j] = distance + w[i]; // 则更新j点的最小距离 heap.push({dist[j], j}); } } } if(dist[n] == 0x3f3f3f3f) return -1; // 起点到不了n点 返回-1 return dist[n];}int main(){ cin >> n >> m; memset(h, -1, sizeof h); while (m -- ){ int a, b, c; cin >> a >> b >> c; add(a, b, c); // a -> b w = c } cout << dijkstra() <
在朴素版dijkstra中寻找距离起点最短的点时，可以使用小根堆优化时间复杂度从O(n) 优化为O(logn) 2.Bellman-Ford算法
通常用来解决：限制边长的最短路问题
【题目链接】ACWing 853.有边数限制的最短路
题目描述
代码如下
#include #include #include using namespace std;const int N = 510, M = 10010;struct Edge { int a; int b; int w;} e[M];//把每个边保存下来即可int dist[N];int back[N];//备份数组防止串联int n, m, k;//k代表最短路径最多包涵k条边int bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i++) { // !!! k次循环： // 每次循环更新：各点到起点 长度为k的最短路 memcpy(back, dist, sizeof dist); for (int j = 0; j < m; j++) {// !!! 遍历所有边 int a = e[j].a, b = e[j].b, w = e[j].w; dist[b] = min(dist[b], back[a] + w); //使用backup:避免给a更新后立马更新b } } return dist[n];}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); e[i] = {a, b, w}; } int res = bellman_ford(); if (dist[n] > 0x3f3f3f / 2) puts("impossible"); else cout << res; return 0;}
3.SPFA算法 ★
简介：
SPFA(Shortest Path Faster Algorithm) 算法是求单源最短路径的一种算法，它是Bellman-ford的队列优化，它是一种十分高效的最短路算法。
优势：
由于SPFA算法是由Bellman_ford算法优化而来，在最坏的情况下时间复杂度和它一样即时间复杂度为 O(nm)。假如题目时间允许，可以直接用SPFA算法去解Dijkstra算法的题目SPFA算法各方面优于Bellman-ford算法，但是在碰到限制了最短路径上边的长度时就只能用bellman_ford了，此时直接把n重循环改成k次循环即可 3.1 SPFA求最短路
引入SPFA：
在Bellman_ford算法中，该算法会遍历图中的所有的边，但是有很多的边遍历了其实没有什么意义，因此可在此处优化。
在SPFA算法中，我们只遍历 到起点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新
因此鉴于此，我们将创建一个队列每一次 加入距离被更新的结点。
C++ 代码如下：
#include #include #include #include using namespace std;const int N = 1e5 + 10;int n, m;int h[N], e[N], w[N], ne[N], idx;int dist[N];bool st[N]; // st数组记录入队的结点void add(int a, int b, int c) { // 添加一条边a->b，边权为c e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}int spfa() { // 求1点到n点的最短距离，如果从1点无法走到n点则返回-1 memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue q; q.push(1); st[1] = true; // 防止队列中存储重复的点、 while(q.size()){ int t = q.front(); q.pop(); st[t] = false; for(int i = h[t]; i != -1; i = ne[i]){ int j = e[i]; if(dist[j] > dist[t] + w[i]){ dist[j] = dist[t] + w[i]; if(!st[j]){ // 如果结点在队列中，则无需入队 q.push(j); st[j] = true; } } } } return dist[n];}int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ){ int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } int t = spfa(); if(dist[n] == 0x3f3f3f3f) cout << "impossible"; else cout<
3.2 SPFA判断负环
题目介绍：
题目链接：ACWing852.spfa判断负环
代码如下
#include #include #include #include using namespace std;const int N = 1e5 + 10;int n, m;int h[N], e[N], w[N], ne[N], idx;int dist[N];int cnt[N]; // 记录最短路径的 边数bool st[N]; // st数组记录入队的结点void add(int a, int b, int c) { // 添加一条边a->b，边权为c e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}bool spfa() { queue q; for(int i = 1; i <= n; i++){ st[i] = true; q.push(i); }// 判断是否存在负环，并非判断是否存在从1开始的负环 // 因此需要将所有的点都加入队列中，更新周围的点 while(q.size()){ int t = q.front(); q.pop(); st[t] = false; for(int i = h[t]; i != -1; i = ne[i]){ int j = e[i]; if(dist[j] > dist[t] + w[i]){ dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; // 更新边数 +1 if(cnt[j] >= n) return true; // 由抽屉原理：无环图n个结点最多n-1条边 // 大于n-1必有环 if(!st[j]){ // 如果结点在队列中，则无需入队 q.push(j); st[j] = true; } } } } return false;}int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ){ int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } if(spfa()) puts("Yes"); else puts("No"); return 0;}