搜索与图论（二） |
您所在的位置：网站首页 › dijesta算法原理 › 搜索与图论（二） |
搜索与图论（二）
|
前言
重学算法第9天，希望能坚持打卡不间断，每天早起学习算法 今日已学完y总的 算法基础课-3.3 第三章 搜索与图论（二） 最短路 共6题，知识点如下： Dijkstra：朴素版Dijkstra求最短路、堆优化版Dijkstra求最短路。 bellman-ford： 有边数限制的最短路。 spfa：spfa求最短路、spfa判断负环。 Floyd：Floyd求最短路。 最短路源点------起点 汇点------终点 n：点数，m：边数 最短路分类 这几个算法，一定要牢记时间复杂度 （可以根据题目条件判断出使用哪个） 可以发现这里没有区分有向图无向图 因为无向图可以看成是两条边的有向图，更新两条边就好了 在每种情况下，都有一种是最好的 图中有负权边时，优先考虑SPFA 都是正数时，如果是稀疏图就用堆优化版Dijkstra，稠密图就用朴素版Dijkstra(其实正数时大部分也可以用SPFA) 多源最短路就用Floy 最短路考察点在建图 这里不对原理做讲解，只对算法的实现思路以及用什么代码模版实现比较好 前面的算法侧重点在于原理，包括后面的数学 但图论侧重点在于代码实现，需要分清 这节课模版比较多，需要课后多背一下 稠密图 用 邻接矩阵存 稀疏图 用 邻接表来存 一个算法只有把代码实现掌握了，才算真的掌握了 因此掌握模版是非常重要的 （不仅要多看多背，还要理解） 不能只停留在理解上的，一定要去写出来 只理解是没意义的，很快就忘了 但多写几遍就不一样了 Dijkstra基于贪心，原理自行百度 朴素dijkstra朴素版时间复杂度与边没有关系 适用于稠密图（边数很多：m接近n^2时，堆优化版比朴素版时间复杂度高）
dist[x] > dist[t] + w； 就是比一下从 1 走到 x 是不是比从 1 走到 t 再到 x 大 如果大就把 x 的距离更新 每次迭代都能确定一个点的最短距离，循环 n 次就能确定每个点到起点的最短距离 模板----朴素dijkstra算法时间复杂是 O(n2) int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i // 1.初始化距离 memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 2.迭代n次 for(int i = 0; i // 1) 如果当前点还没确定最短路，或者当前的t不是最短的 if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 即在所有s[j] == false的点中，找到dist最小的点 } // 2)将t加到集合中 st[t] = true; // 3)用t更新到其他点的距离 for (int j = 1; j scanf("%d%d", &n, &m); // 初始化 memset(g, 0x3f, sizeof g); while (m --) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a][b] = min(g[a][b], c); //如果有重边，只保留最短的那条边 } int t = dijkstra(); printf("%d\n", t); return 0; } 堆优化版dijkstra堆优化版 用堆对朴素版进行的优化
优先队列不支持修改任意元素的操作，所以可能会有冗余 但时间复杂度实际上是一个级别的 所以一般不用自己手写堆 如果找到的最小值已经确定过了，扔掉就好 用st[]判断一下，直接continue 模板----堆优化版dijkstra时间复杂度 O(mlogn), n 表示点数，m 表示边数 typedef pair PII; int n; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 // 求1号点到n号点的最短距离，如果不存在，则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue heap; heap.push({0, 1}); // first存储距离，second存储节点编号 while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; 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]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } 模板题 AcWing 850. Dijkstra求最短路 II #include #include #include #include using namespace std; typedef pair PII; // 稀疏图，用邻接表 const int N = 1e6 + 10; int n, m; int h[N], w[N], e[N], ne[N], idx; // 邻接表存, w表示权重 int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; } int dijkstra() { // 1.初始化距离 memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 小根堆(用优先队列维护所有点的距离)【语法，背过即可】 priority_queue heap; heap.push({0, 1}); // 起点 // 队列不空时 while(heap.size()) { auto t = heap.top(); heap.pop(); // 每次取出当前距离最小的点 // 第一个存距离，第二个存编号 int distance = t.first, ver = t.second; if (st[ver]) continue; // 之前更新过说明是冗余的，跳过 st[ver] = true; // 一定要加上这行，否词会有用例超时 // 没更新过就用这个点更新其他所有点的最短距离 for (int i = h[ver]; i != - 1; i = ne[i]) { int j = e[i]; // j存储编号 if (dist[j] > distance + w[i]) { // 当前点的距离dist[j] 比从t过来要大就更新 // 更新成功就加入队列 dist [j] = distance + w[i]; heap.push({dist[j], j}); // 将j放入优先队列 } } } if (dist[n] == 0x3f3f3f3f) return -1; // 说明1和n是不连通的 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 = dijkstra(); printf("%d\n", t); return 0; } bellman-ford也比较简单，实现就那么几行 循环结束后一定满足 dist[b] memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] > dist[a] + w) dist[b] = dist[a] + w; } } if (dist[n] > 0x3f3f3f3f / 2) return -1; return dist[n]; } 模板题 AcWing 853. 有边数限制的最短路 限制了边的个数，有负环也无所谓了 该题只能用bellman-ford算法来做，不用spfa
比如此时限制边为 1，则 1 —>3的最短距离为 3 备份恢复到上一步就不会发生串联了 #include #include #include using namespace std; const int N = 510, M = 10010; int n, m, k; int dist[N], backup[N];// backup[N]：备份，防止串联 struct Edge { int a, b, w; }edges[M]; int bellman_ford() { // 一定要记得初始化 memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i int a = edges[j].a, b = edges[j].b, w= edges[j].w; dist[b] = min(dist[b], backup[a] + w); // 只用上一次迭代的结果更新当前距离 } } if (dist[n] > 0x3f3f3f3f / 2) return NULL; // 不返回-1的原因是可能存在负权边，最后加起来t的值为-1 return dist[n]; } int main() { scanf ("%d%d%d", &n, &m, &k); for (int i = 0; i a, b, w}; } int t = bellman_ford(); if (t == NULL) puts("impossible"); else printf("%d\n", t); return 0; }最后为什么是dist[n] > 0x3f3f3f3f / 2？ 如图，虽然可能到不了，但会更新最小值为0x3f3f3f3f减去一个数
一般情况只要没有负环，就可以用spfa （很多正权图的题，拿spfa也可以过掉） 与Dijkstra的代码非常像 虽然是bellman-ford的优化，但并不是所有情况都可以用 如：经过的边数 auto 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]) // 如果队列中已存在j，则不需要将j重复插入 { q.push(j); st[j] = true; } } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } 模板题 AcWing 851. spfa求最短路 #include #include #include #include using namespace std; typedef pair PII; const int N = 100010; int n, m; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; } int spfa() { // 初始化所以点的距离 memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue q; q.push(1); st[1] = true; // st存的是当前点是否在队列中，防止存无意义的重复点 // 不空 while (q.size()) { int t = q.front(); q.pop(); // 点从队列中出来了，更新为false 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]) { // 如果j不在队列中才需要加入 q.push(j); st[j] = true; } } } } // if (dist[n] == 0x3f3f3f3f) return -1; 如果返回答案为-1就不行，直接合并到下面较为方便 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 (t == -1) puts("impossible"); if (t == 0x3f3f3f3f) puts("impossible"); else printf("%d\n", t); return 0; } spfa代码也可把Dijkstra的题过掉，如果不卡的话，卡了就还是得用优化版的Dijkstra 笔试题一般不会卡 spfa判断负环需要更新最短距离的时候，顺带更新 cnt，即1 --> t 的边数 +1
时间复杂度是 O(nm), n 表示点数，m 表示边数 int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数 bool st[N]; // 存储每个点是否在队列中 // 如果存在负环，则返回true，否则返回false。 bool spfa() { // 不需要初始化dist数组 // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。 queue q; for (int i = 1; i auto 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; if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环 if (!st[j]) { q.push(j); st[j] = true; } } } } return false; } 模板题 AcWing 852. spfa判断负环 #include #include #include #include using namespace std; typedef pair PII; const int N = 100010; int n, m; int h[N], w[N], e[N], ne[N], idx; int dist[N], cnt[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; } bool spfa() { // 求的是负环，不需要初始化距离 queue q; // 将所有点全部放入队列中，因为如果从1开始可能走不到负环 for (int i = 1; i int t = q.front(); q.pop(); // 点从队列中出来了，更新为false 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[j] + 1; if (cnt[j] >= n) return true; 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; } Floyd非常简单 原理基于 动态规划 也不能有负权回路
三重循环可以把邻接矩阵直接变成最短距离矩阵 d[i,j]存的就是 i 到 j 的最短路径长度 注意要先循环k，i 和 j 的顺序无所谓 模板时间复杂度是 O(n3), n 表示点数 初始化： for (int i = 1; i for (int k = 1; k for (int j = 1; j scanf("%d%d%d", &n, &m, &Q); // 初始化邻接矩阵,重边保留最小的，自环直接删去即可 for (int i = 1; i if (i == j) d[i][j] = 0; // else d[i][j] = INF; } } // 读入每条边 while(m --) { int a, b, w; scanf("%d%d%d", &a, &b, &w); // 如果有多条边，保留最小的 d[a][b] = min(d[a][b], w); } floyd(); // 询问 while(Q -- ) { int a, b; scanf("%d%d", &a, &b); // 此处要除二的原因与之前相同, // ab直接不存在通路，如果存在负权边，最短距离不一定是正无穷，可能会小一些 if (d[a][b] > INF / 2) puts("impossible"); else printf("%d\n", d[a][b]); } return 0; }
尤其是动态规划相关的题目 调试代码方法一般就两种 1.直接cout 2.删代码法 至于怎么快速调出来就主要就看经验了， 刷题刷多了，调多了，就快了 学算法一定要多写代码 学完基础课后 使用限时功能（不能复制粘贴，只能自己敲） 好好练习一下题目 速度提高了算法水平也就提高了 |
只用考虑有向图即可
w：权重
如果不备份，会在上一步的结果上继续下一步（串联），就不满足限制k条边了，
如果某次循环中，cnt[x] >= n了，说明有 n 条边，即 n+1 个点，而本身只有 n 个点，就确定存在负环了 
思路比画图模拟更重要，要从整体上去看思路是什么【本文地址】
今日新闻 |
推荐新闻 |