网站建设类型有哪些,.net做的学校网站,宜春建设局官方网站,wordpress 二次开发 pdf#x1f600;大家好#xff0c;我是白晨#xff0c;一个不是很能熬夜#x1f62b;#xff0c;但是也想日更的人✈。如果喜欢这篇文章#xff0c;点个赞#x1f44d;#xff0c;关注一下#x1f440;白晨吧#xff01;你的支持就是我最大的动力#xff01;#x1f4…大家好我是白晨一个不是很能熬夜但是也想日更的人✈。如果喜欢这篇文章点个赞关注一下白晨吧你的支持就是我最大的动力 文章目录前言最短路算法️Dijkstra朴素Dijkstra算法堆优化Dijkstra算法️Bellman-Ford有边数限制的最短路️SPFASPFA求最短路SPFA判断负环FloydFloyd求最短路后记前言 咕咕咕我是白晨最近一直在忙开学考试托更了很久果咩纳塞。 这次为大家分享的是图论中的最短路算法。考虑到最短路算法的复杂性以及本文新手向的教程本次算法讲解列举了大量例子并且配上了大量动图。本篇文章所有的代码实现都是算法向的以快速实现和效率为主如果出现算法向的代码实在看不懂可以参考白晨的工程向实现的代码工程向代码链接Graph。 最短路算法 最短路算法是指 一个图中求某一个节点到其他节点的最短路径最小权值路径的算法。 最短路算法是图论中一类很重要的算法也是算法题中经常会使用的一类算法。这种算法也可以和实际问题结合起来比如 你要从西安到上海要找到用时最短的一条路径就需要这种算法。 ️Dijkstra 朴素Dijkstra算法 原题链接Dijkstra求最短路 I
算法思想 朴素Dijkstra算法为单源最短路算法适合稠密图时间复杂度为 O(n2)O(n^2)O(n2) n为节点个数对于边的存储结构为 邻接矩阵。 注意Dijkstra算法必须要保证所有边的权值为正否则算法的贪心策略证明失效。
具体做法
初始化 dist 数组初始化为无限大 以及 dist[1]0dist[1] 0dist[1]0一号节点到自己的距离为0。遍历 dist 数组选出其中距离最短的节点选中此节点加入已确定最短距离的节点的集合S。根据上面确定节点的最短距离 更新 到达其他节点的最短距离S集合中节点距离不可能再被更新。重复2、3过程 N 次N次迭代后全部点的最短距离已经被确定。
以上的思想本质上来说是一种贪心策略为什么能保证每次选中的距离1号节点最近的节点的路径就是最短路径呢 Dijsktra迪杰斯特拉算法的证明数学归纳法和代码实现 证明见上面文章。
现在我们来模拟一下Dijkstra算法的具体流程 动画演示如下 代码实现
// 朴素Dijkstra算法
#include iostream
#include cstringusing 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)O(mlogn)O(mlogn)m为边数n为节点数边的存储结构为邻接表。 相比于朴素版本算法对于寻找路径最短的节点的过程进行了优化改为了用小根堆堆存储最短路径根据小根堆的特性最短的路径就是堆顶元素这样就省去了寻找最短路径的过程。
注意Dijkstra算法必须要保证所有边的权值为正否则算法的贪心策略证明失效。
具体做法 初始化 dist 数组dist[1]0dist[1] 0dist[1]0将{0,1}距离为0节点序号为1入堆。出堆顶元素根据新确定最短路径以及节点下标更新其他路径本次选用的存储结构为邻接表所以直接遍历每个节点对应的链表即可。重复2过程直到堆为空。
代码实现
// 堆优化Dijkstra算法
#include iostream
#include queue
#include cstringusing namespace std;typedef pairint, int PII;const int N 150010, INF 0x3f3f3f3f;int n, m;// 这里只是我习惯的邻接表存储方式也可以用结构体存储只要能遍历一个节点的所有出边就可以
int g[N], e[N], ne[N], val[N], idx;// g为邻接表eneval为单链表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_queuePII, vectorPII, greaterPII 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)O(nm)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 cstringusing 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-12-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(m)O(m)最坏为O(nm)O(nm)O(nm)本算法优化了Bellman-Ford算法每次遍历全部边的过程本质上是 BFS 边的存储结构为 邻接矩阵。 核心思路只有 dist[a] 更新了 a-b 边才会被使用否则不会使用a-b这条边所以本算法存储更新过的最短路很像Dijkstra堆优化版本。 具体做法 初始化dist数组dist[1]0dist[1] 0dist[1]0将1号节点其入队。广度优先搜索出队节点元素遍历每个节点的出边更新直到队列为空。
SPFA算法动画演示 代码实现
// SPFA
#include iostream
#include queue
#include cstringusing 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;queueint 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]ncnt[i] ncnt[i]n说明路径中出现环如果出现环一定是负环因为正环不会 dist[i]环的路径dist[i]dist[i] 环的路径 dist[i]dist[i]环的路径dist[i] 也就不会被更新。
如何证明cnt[i]ncnt[i] ncnt[i]n就一定出现环呢
反证法如果cnt[i]ncnt[i] ncnt[i]n没有环说明从1到 i 没有走过任何一个重复的节点但是一共只有n个节点当有n条边时连接了n1个节点根据抽屉原理必定有相同的节点所以必定有环。
代码实现
// SPFA
#include iostream
#include queue
#include cstringusing 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数组不表示最短距离可以不需要初始化这样更新的就只有负权边了queueint 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(n3)O(n^3)O(n3)本质上是区间动态规划核心代码只有四行非常牛。边的存储结构邻接矩阵。 状态f[i,j,k]f[i, j, k]f[i,j,k]表示从iii走到jjj的路径上除了iii和jjj以外 只经过1∼k1\sim k1∼k号节点 的所有路径的最短距离。eg.f[5,6,3]f[5, 6, 3]f[5,6,3]表示 从555号节点走到666号节点 只经过 123123123 这三个节点的最短距离 最初状态f[i,j,k]∞f[i, j, k] \inftyf[i,j,k]∞ 状态转移方程f[i,j,k]min(f[i,j,k],f[i,k,k−1]f[k,j,k−1])f[i, j, k] min(f[i, j, k], f[i, k, k - 1] f[k, j, k -1])f[i,j,k]min(f[i,j,k],f[i,k,k−1]f[k,j,k−1])iii节点到jjj节点只经过1∼k1\sim k1∼k号节点的最短距离等于 本身原值 和 iii节点到kkk节点只经过1∼k−11 \sim k-11∼k−1号节点最短距离和kkk节点到j节点只经过1∼k−11\sim k-11∼k−1号节点最短距离之和的最小值。
由于状态转移中k层状态只需要用到k-1层状态所以k这一维可以被优化掉。
代码实现
// Floyd算法
#include iostream
#include cstringusing 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(n2)O(n^2)O(n2) n为节点个数对于边的存储结构为 邻接矩阵。堆优化Dijkstra贪心算法必须保证无负权边适用于稀疏图时间复杂度为 O(mlogn)O(mlogn)O(mlogn)m为边数n为节点数边的存储结构为邻接表。Bellman-Ford循环遍历时间复杂度为 O(nm)O(nm)O(nm)顶点数*边数所以边的存储不做要求只要能遍历到全部边就可以可以用结构体也可以用邻接表等。SPFABFS时间复杂度一般为O(m)O(m)O(m)最坏为O(nm)O(nm)O(nm)边的存储结构为 邻接矩阵。 多元最短路算法 Floyd动态规划时间复杂度为O(n3)O(n^3)O(n3)边的存储结构为邻接矩阵。 如果解析有不对之处还请指正我会尽快修改多谢大家的包容。
如果大家喜欢这个系列还请大家多多支持啦
如果这篇文章有帮到你还请给我一个大拇指 和小星星 ⭐️支持一下白晨吧喜欢白晨【算法】系列的话不如关注白晨以便看到最新更新哟
我是不太能熬夜的白晨我们下篇文章见。 文章转载自： http://www.morning.sfwfk.cn.gov.cn.sfwfk.cn http://www.morning.jrqw.cn.gov.cn.jrqw.cn http://www.morning.mrxqd.cn.gov.cn.mrxqd.cn http://www.morning.wsyq.cn.gov.cn.wsyq.cn http://www.morning.shxrn.cn.gov.cn.shxrn.cn http://www.morning.ymjrg.cn.gov.cn.ymjrg.cn http://www.morning.rmfh.cn.gov.cn.rmfh.cn http://www.morning.yjqkk.cn.gov.cn.yjqkk.cn http://www.morning.yjprj.cn.gov.cn.yjprj.cn http://www.morning.nnmnz.cn.gov.cn.nnmnz.cn http://www.morning.rnfn.cn.gov.cn.rnfn.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.ztcxx.com.gov.cn.ztcxx.com http://www.morning.ljxxl.cn.gov.cn.ljxxl.cn http://www.morning.hxrfb.cn.gov.cn.hxrfb.cn http://www.morning.nwynx.cn.gov.cn.nwynx.cn http://www.morning.thrgp.cn.gov.cn.thrgp.cn http://www.morning.jkpnm.cn.gov.cn.jkpnm.cn http://www.morning.xtdms.com.gov.cn.xtdms.com http://www.morning.lzbut.cn.gov.cn.lzbut.cn http://www.morning.zdhxm.com.gov.cn.zdhxm.com http://www.morning.pjbhk.cn.gov.cn.pjbhk.cn http://www.morning.qbksx.cn.gov.cn.qbksx.cn http://www.morning.smrty.cn.gov.cn.smrty.cn http://www.morning.kgtyj.cn.gov.cn.kgtyj.cn http://www.morning.pngph.cn.gov.cn.pngph.cn http://www.morning.rnxs.cn.gov.cn.rnxs.cn http://www.morning.cpctr.cn.gov.cn.cpctr.cn http://www.morning.wcjgg.cn.gov.cn.wcjgg.cn http://www.morning.mbfj.cn.gov.cn.mbfj.cn http://www.morning.fchkc.cn.gov.cn.fchkc.cn http://www.morning.cwskn.cn.gov.cn.cwskn.cn http://www.morning.mbrbg.cn.gov.cn.mbrbg.cn http://www.morning.ltdxq.cn.gov.cn.ltdxq.cn http://www.morning.bksbx.cn.gov.cn.bksbx.cn http://www.morning.qnywy.cn.gov.cn.qnywy.cn http://www.morning.csdgt.cn.gov.cn.csdgt.cn http://www.morning.stbfy.cn.gov.cn.stbfy.cn http://www.morning.wkkqw.cn.gov.cn.wkkqw.cn http://www.morning.zrlms.cn.gov.cn.zrlms.cn http://www.morning.pzss.cn.gov.cn.pzss.cn http://www.morning.wqcz.cn.gov.cn.wqcz.cn http://www.morning.gnyhc.cn.gov.cn.gnyhc.cn http://www.morning.sgrdp.cn.gov.cn.sgrdp.cn http://www.morning.hksxq.cn.gov.cn.hksxq.cn http://www.morning.przc.cn.gov.cn.przc.cn http://www.morning.qztsq.cn.gov.cn.qztsq.cn http://www.morning.pzjrm.cn.gov.cn.pzjrm.cn http://www.morning.cknws.cn.gov.cn.cknws.cn http://www.morning.xcszl.cn.gov.cn.xcszl.cn http://www.morning.cbnjt.cn.gov.cn.cbnjt.cn http://www.morning.cnyqj.cn.gov.cn.cnyqj.cn http://www.morning.jmdpp.cn.gov.cn.jmdpp.cn http://www.morning.cwpny.cn.gov.cn.cwpny.cn http://www.morning.dmfdl.cn.gov.cn.dmfdl.cn http://www.morning.pftjj.cn.gov.cn.pftjj.cn http://www.morning.hpmzs.cn.gov.cn.hpmzs.cn http://www.morning.sgbjh.cn.gov.cn.sgbjh.cn http://www.morning.dpplr.cn.gov.cn.dpplr.cn http://www.morning.mknxd.cn.gov.cn.mknxd.cn http://www.morning.bsjpd.cn.gov.cn.bsjpd.cn http://www.morning.qqnjr.cn.gov.cn.qqnjr.cn http://www.morning.jnhhc.cn.gov.cn.jnhhc.cn http://www.morning.jgncd.cn.gov.cn.jgncd.cn http://www.morning.kfstq.cn.gov.cn.kfstq.cn http://www.morning.ygth.cn.gov.cn.ygth.cn http://www.morning.jbmbj.cn.gov.cn.jbmbj.cn http://www.morning.gyfwy.cn.gov.cn.gyfwy.cn http://www.morning.ypbdr.cn.gov.cn.ypbdr.cn http://www.morning.jjnql.cn.gov.cn.jjnql.cn http://www.morning.bpmdn.cn.gov.cn.bpmdn.cn http://www.morning.ljxps.cn.gov.cn.ljxps.cn http://www.morning.wqpr.cn.gov.cn.wqpr.cn http://www.morning.rlnm.cn.gov.cn.rlnm.cn http://www.morning.gwsdt.cn.gov.cn.gwsdt.cn http://www.morning.przc.cn.gov.cn.przc.cn http://www.morning.dgckn.cn.gov.cn.dgckn.cn http://www.morning.rtpw.cn.gov.cn.rtpw.cn http://www.morning.zcfmb.cn.gov.cn.zcfmb.cn http://www.morning.rfpb.cn.gov.cn.rfpb.cn
