上一期介绍到了 SPFA 算法, 只是一笔带过, 这一期让我们详细的介绍一下 SPFA.
1 SPFA 原理介绍
SPFA 算法和 dijkstra 算法特别像, 总感觉自己讲的不行, 同学说我的博客很辣鸡, 推荐一个视频讲解, 想看点这里 https://www.bilibili.com/video/av11124486/ , 算法思路如下:
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=1;i<=n;i++)
- dis[i]=inf;
- queue<int>q;
- q.push(1);vis[1]=1;dis[1]=0;
- while(q.size())
- {
- x=q.front();q.pop();vis[x]=0;
- 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]==0)
- {
- vis[s]=1;
- q.push(s);
- }
- }
- }
- }
- }
来源: https://www.cnblogs.com/TFLS-gzr/p/10387463.html