【最短路径】 SPFA算法
2024-08-30 00:16:54
上一期介绍到了SPFA算法,只是一笔带过,这一期让我们详细的介绍一下SPFA。
1 SPFA原理介绍
SPFA算法和dijkstra算法特别像,总感觉自己讲的不行,同学说我的博客很辣鸡,推荐一个视频讲解,想看点这里,算法思路如下:
1)和dijkstra一样初始化,定义一个dis[ ]数组,除了源点赋成0之外其它点都赋成正无穷,然后定义一个队列q。
2)把队列q的队首元素取出,标志为不在队中,将其作为中继点对这个队首元素的所有出边进行松弛操作(不知道松弛操作请看这里),修改完dis值后,判断每一个修改过dis值的元素是否在队列q中,如果不在,就放入队尾;然后判断这个数入队的次数,如果大于n(n为点的个数),那就说明出现了负权回路,算法结束,否则继续。
3)不断循环,直到队列为空。
2 实现过程中的一些问题
- question:怎么标志出队?
answer:可以定义一个vis[ ]数组,最开始全部为0,表示都不在队列中,每入队一个元素x,就把vis[x]赋成1,每出队一个元素就赋值成0。
- question:怎么判断一个数入队次数?
answer:可以定义一个num[ ]数组,每入队一个元素x,就num[x]++;这个可以不写,因为题目一般不会出现负权回路。
- question:怎么判断队列为空?
answer:最流行的写法是while(!q.empty()),但是不太好理解,我一般会写成while(s.size()),和前一句意思相同。
3 图解演示
//这个图解做了一上午,可能讲的不好,不喜勿喷
4 代码奉上:
void SPFA()
{
for(int i=;i<=n;i++)
dis[i]=inf;
queue<int>q;
q.push();vis[]=;dis[]=;
while(q.size())
{
x=q.front();q.pop();vis[x]=;
for(int i=head[x];i;i=a[i].next)
{
int s=a[i].to;
if(dis[s]>dis[x]+a[i].cost)
{
dis[s]=dis[x]+a[i].cost;
if(vis[s]==)
{
vis[s]=;
q.push(s);
}
}
}
}
}
5 算法优化
新更博客:SPFA算法优化
最新文章
- Jquery plupload上传笔记(修改版)
- jquery Ajax的load、post、get、put、delete的用法
- ServletContentLIstener接口演示ServletContext的启动和初始化
- POJ 3311 Hie with the Pie(DP状态压缩+最短路径)
- Diet
- BZOJ 3439: Kpm的MC密码( trie + DFS序 + 主席树 )
- cocos2d-x游戏开发 跑酷(四) 关联与物理世界
- Ninject 在 Winform、 Asp.net MVC中连络EntityFramework的应用
- HDU 5890 Eighty seven
- 随机生成并排序 C,去同,有序数组合并排序
- QT 的使用及编写代码遇到的问题和解决方法
- H5游戏见缝插针开发
- Spring Boot 读取 resource 下文件
- 28. SpringBoot 集成Redis
- Django学习手册 - 权限管理(二)
- win10安装JDK
- OEMCC13.2 添加监控目标
- fastjson的常用方法
- 08 - JavaSE之IO流
- Samsung_tiny4412(驱动笔记09)----alloc_pages,kmalloc,vmalloc,kmem_cache,class