Bellman-ford算法、SPFA算法求解最短路模板
2024-08-30 12:23:27
Bellman-ford 算法适用于含有负权边的最短路求解,复杂度是O( VE ),其原理是依次对每条边进行松弛操作,重复这个操作E-1次后则一定得到最短路,如果还能继续松弛,则有负环。这是因为最长的没有环路的路,也只不过是V个点E-1条边构成的,所以松弛E-1次一定能得到最短路。因此这个算法相比 Dijkstra 首先其是对边进行增广,其次它能检测出负环的存在(若负环存在,那么最短路是取不到的,因为可以一直绕着这个负环将最小路径值不断缩小),这个弥补了 Dijkstra 的不足,但是其算法跑的比较慢,因此为了追求速度往往采用其“队列优化版”==>SPFA,因此想要理解SPFA最好先看看Bellman-ford算法。
SPFA 算法适用于含有负权边的最短路求解,其复杂度并没有网上传的那么神乎在理想情况下有论文指出其复杂度为O(kE)且k是一个约小于2的常数,但是在一些稠密图下其算法性能还是会退化到和 Bellman-ford 一样的 O( VE ),所以在稠密图下建议使用 Dij + Heap 优化的版本,稀疏图下 SPFA 还是很给力的!在 Bellman-ford 中发现啊最外层的 N-1 次循环未免盲目、实际上被松弛过的点我们希望其去继续松弛其他点,这样我们用队列将被松弛过的点存起来以便下一次继续松弛其他点,具体原理和做法可以参考下面的链接,顺便一提,SPFA还有两个优化==> SLF 与 LLL,具体也不阐述了。本文主要给出模板!
算法原理 or 学习参考链接 : 点我 、点我啦 、 点嘛!
Bellman-ford模板
///POJ 2387为例 #include<bits/stdc++.h> using namespace std; ; const int INF = 0x3f3f3f3f; struct EdgeNode{ int from, to, w; }; EdgeNode Edge[maxn*maxn]; int Dis[maxn]; int N, M, cnt; inline void init() { ; i<=N; i++) Dis[i] = INF; cnt = ; } bool BellmanFord(int st) { Dis[st] = ; ; i<N; i++){///N-1 次循环后肯定能找出最短路 bool Changed = false; int to, from, weight; ; j<cnt; j++){ to = Edge[j].to, from = Edge[j].from, weight = Edge[j].w; if(Dis[from]!=INF && Dis[to] > Dis[from] + weight){ Changed = true; Dis[to] = Dis[from] + weight; ///pre[to] = j; //Record paths } } if(!Changed) return true;///如果没有边可以继续松弛了,说明算法结束且无负环 if(i==N && Changed) return false;///有负环 } return false; ///一般来说绝无可能执行到这一步 } int main(void) { while(~scanf("%d %d", &M, &N)){ init(); int from, to, weight; ; i<M; i++){ scanf("%d %d %d", &from, &to, &weight); Edge[cnt].from = from; Edge[cnt].to = to; Edge[cnt].w = weight; cnt++; Edge[cnt].to = from; Edge[cnt].from = to; Edge[cnt].w = weight; cnt++; } BellmanFord(); printf("%d\n", Dis[N]); } ; }
SPFA模板( SLF 优化版 )
///POJ 2387为例 #include <iostream> #include <cstdio> #include <cmath> #include <queue> #include <string.h> using namespace std; const int INF=0x3f3f3f3f; ; struct EdgeNode{ int v, w, nxt; }; EdgeNode Edge[maxn*maxn]; bool vis[maxn]; int Head[maxn], Dis[maxn], cnt; int N, M; /// int PushCnt[maxn]; ///记录每一个节点的入队次数、方便判断负环 inline void init() { ; i<=N; i++) ///PushCnt[i] = 0; Head[i] = -, Dis[i] = INF, vis[i] = false; cnt = ; } inline void AddEdge(int from, int to, int weight) { Edge[cnt].w = weight; Edge[cnt].v = to; Edge[cnt].nxt = Head[from]; Head[from] = cnt++; } void SPFA(int st)///若要判断负环、改为 bool { deque<int> que; que.push_back(st); vis[st]=true; Dis[st]=; while (!que.empty()) { int T=que.front(); que.pop_front(); vis[T]=false; ; i=Edge[i].nxt) { int v=Edge[i].v; int w=Edge[i].w; if (Dis[v]>Dis[T]+w){ Dis[v]=Dis[T]+w; ///p[v] = T; if (!vis[v]){ ///if(++PushCnt[v] > N) return false; //有负环 vis[v]=true; if(!que.empty() && Dis[v] < Dis[que.front()]) que.push_front(v); else que.push_back(v); //que.push_back(v); ///无SLF优化是这样写的 } } } } /// return true; } int main(void) { while(~scanf("%d %d", &M, &N)){ init(); int from, to, weight; ; i<M; i++){ scanf("%d %d %d", &from, &to, &weight); AddEdge(from, to, weight); AddEdge(to, from, weight); } SPFA(); printf("%d\n", Dis[N]); } ; }
最新文章
- IOS程序开发中-跳转到 发送短信界面 实现发短信
- php构造函数,引入数据库操作类函数
- 服务器文件系统一定要用NTFS格式。
- Env:Winmanager插件使用
- 【英语】Bingo口语笔记(3) - 无所谓
- MiZ702学习笔记13——ZYNQ通过AXI-Lite与PL交互
- vs开发工具使用问题
- 学习MVC之租房网站(二)-框架搭建及准备工作
- JavaScript正则表达式检验与递归函数实际应用
- Mycat 分片规则详解--单月小时分片
- iOS监听模式系列之对APNs的认知与理解
- Spring 学习笔记 Bean的作用域
- Vue 路由心得总结
- hive group by聚合函数增强
- 【AtCoder078D】Fennec VS. Snuke
- koa2框架设置响应和请求头
- Spring事务原理
- tf 数据读取
- 难度2:ASCII码排序
- 【POJ2411】Mondriaan&#39;s Dream(轮廓线DP)
热门文章
- 应用安全 - 无文件式攻击 - 潜伏型攻击 - MBR - 汇总 (2019-11-29 15:57)
- 应用安全 - 软件漏洞 - sudo漏洞汇总
- Python_ONLINE_习题集_1 递归
- python 并发编程 多进程 守护进程
- linux工具之screen
- qt 获取磁盘空间大小,cpu利用率,内存使用率
- Javascript的是三种字符串连接方式
- 02: CI(持续集成)/CD(持续交付/持续部署)
- python day1-requests
- 小白学Python(20)—— Turtle 海龟绘图