Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【最短路径】 SPFA算法

c1714-gzr 2019-02-16 13:28:00 阅读数:163 评论数:0 点赞数:0 收藏数:0

上一期介绍到了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 代码奉上:

 1 void SPFA()
 2 {
 3 for(int i=1;i<=n;i++)
 4 dis[i]=inf;
 5 queue<int>q;
 6 q.push(1);vis[1]=1;dis[1]=0;
 7 while(q.size())
 8  {
 9 x=q.front();q.pop();vis[x]=0;
10 for(int i=head[x];i;i=a[i].next)
11  {
12 int s=a[i].to;
13 if(dis[s]>dis[x]+a[i].cost)
14  {
15 dis[s]=dis[x]+a[i].cost;
16 if(vis[s]==0)
17  {
18 vis[s]=1;
19  q.push(s);
20  }
21  }
22  }
23  }
24 }

 5 算法优化

新更博客:SPFA算法优化

版权声明
本文为[c1714-gzr]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/TFLS-gzr/p/10387463.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领