tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

spfa算法详解


SPFA 算法详解

适用范围: 给定的图存在负权边,这时类似 Dijkstra 等算法便没有了用武之地, 而 Bellman-Ford 算法的复杂度又过高,SPFA 算法便 派上用场了。 我们约定有 向加权图 G 不存在负权回路,即最短路径一定存在。当然,我们可以在执行该算 法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点。 算法思想: 我

们用数组 d 记录每个结点的最短路径估计值, 用邻接表来存储图 G。 我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的 结 点,优化时每次取出队首结点 u,并且用 u 点当前的最短路径估计值对离开 u 点 所指向的结点 v 进行松弛操作, 如果 v 点的最短路径估计值有所调整,且 v 点不 在 当前的队列中,就将 v 点放入队尾。这样不断从队列中取出结点来进行松弛 操作,直至队列空为止。

期望的时间复杂度 O(ke), 其中 k 为所有顶点进队的平均次数,可以证明 k 一 般小于等于 2。

实现方法: 建立一个队列, 初始时队列里只有起始点,再建立一个表格记录起始点到所 有点的最短路径 (该表格的初始值要赋为极大值, 该点到他本身的路径赋为 0) 。 然后执行松弛操作, 用队列里有的点作为起始点去刷新到所有点的最短路,如果 刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列 为空。 判断有无负环: 如果某个点进入队列的次数超过 N 次则存在负环(SPFA 无法处理带负环的 图)

首先建立起始点 a 到其余各点的 最短路径表格

首先源点 a 入队,当队列非空时: 1、队首元素(a)出队,对以 a 为起始点的所有边的终点依次进行松弛操作 (此处有 b,c,d 三个点),此时路径表格状态为:

在松弛时三个点的最短路径估值变小了,而这些点队列中都没有出现,这些点 需要入队,此时,队列中新入队了三个结点 b,c,d 队首元素 b 点出队, 对以 b 为起始点的所有边的终点依次进行松弛操作(此处只 有 e 点),此时路径表格状态为:

在最短路径表中,e 的最短路径估值也变小了,e 在队列中不存在,因此 e 也要 入队,此时队列中的元素为 c,d,e 队首元素 c 点出队, 对以 c 为起始点的所有边的终点依次进行松弛操作(此处有 e,f 两个点),此时路径表格状态为:

在最短路径表中,e,f 的最短路径估值变小了,e 在队列中存在,f 不存在。因 此 e 不用入队了,f 要入队,此时队列中的元素为 d,e,f 队首元素 d 点出队, 对以 d 为起始点的所有边的终点依次进行松弛操作(此处 只有 g 这个点),此时路径表格状态为:

在最短路径表中,g 的最短路径估值没有变小(松弛不成功),没有新结点入队, 队列中元素为 f,g 队首元素 f 点出队, 对以 f 为起始点的所有边的终点依次进行松弛操作(此处有 d,e,g 三个点),此时路径表格状态为:

在最短路径表中,e,g 的最短路径估值又变小,队列中无 e 点,e 入队,队列中 存在 g 这个点,g 不用入队,此时队列中元素为 g,e 队首元素 g 点出队, 对以 g 为起始点的所有边的终点依次进行松弛操作(此处只 有 b 点),此时路径表格状态为:

在最短路径表中,b 的最短路径估值又变小,队列中无 b 点,b 入队,此时队列 中元素为 e,b 队首元素 e 点出队, 对以 e 为起始点的所有边的终点依次进行松弛操作(此处只 有 g 这个点),此时路径表格状态为:

在最短路径表中,g 的最短路径估值没变化(松弛不成功),此时队列中元素为 b 队首元素 b 点出队, 对以 b 为起始点的所有边的终点依次进行松弛操作(此处只 有 e 这个点),此时路径表格状态为:

在最短路径表中,e 的最短路径估值没变化(松弛不成功),此时队列为空了 最终 a 到 g 的最短路径为14

program: #include<cstdio> using namespace std; struct node {int x; int value; int next; }; node e[60000]; int visited[1505],dis[1505],st[1505],queue[1000]; int main() { int n,m,u,v,w,start,h,r,cur; freopen("c.in","r",stdin); freopen("c.out","w",stdout); while(scanf("%d%d",&n,&m)!=EOF) {

for(int i=1;i<=1500;i++) {visited[i]=0; dis[i]=-1; st[i]=-1; //这个初始化给下边那个 while 循环带来影响 } for(int i=1;i<=m;i++) { scanf("%d%d%d\n",&u,&v,&w); e[i].x=v; //记录后继节点 相 当于链表中的创建一个节点,并使得数据域先记录 e[i].value=w; e[i].next=st[u]; //记录顶点节点的某一个边表节点 的下标,相当于在链表中吧该边表节点的 next 指针先指向他的后继边表节点 st[u]=i; //把该顶点的指针 指向边表节点,相当于链表中的插入中,头结点的指针改变 } start=1; visited[start]=1; dis[start]=0; h=0; r=1; queue[r]=start; while(h!=r) { h=(h+1)%1000; cur=queue[h]; int tmp=st[cur]; visited[cur]=0;

while(tmp!=-1) { if (dis[e[tmp].x]<dis[cur]+e[tmp].value) //改成大 于号才对 { dis[e[tmp].x]=dis[cur]+e[tmp].val ue; if(visited[e[tmp].x]==0) { visited[e[tmp].x ]=1;

r=(r+1)%1000; queue[r]=e[tmp] .x; } } tmp=e[tmp].next; } } printf("%d\n",dis[n]); } return 0; }


推荐相关:

SPFA算法简介

SPFA算法简介_IT/计算机_专业资料。SPFA 算法简介 算法采用图的存储结构是邻接表...SPFA单源最短路算法讲解 4页 免费 SPFA 2页 免费 SPFA算法的优化及应用 37页...


SPFA算法的优化及应用

37 - 第 2 页共 37 页 - 2009Thesis SPFA 的优化与应用 姜碧野 【正文】 SPFA 算法简介 1.1 SPFA 算法的基本实现下面,先介绍一下 SPFA 和 Bellman-Ford...


spfa

17页 免费 SPFA 4页 免费 算法合集之《最短路算法及... 30页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


邻接表的构造以及SPFA模板

邻接表的构造以及SPFA模板_计算机软件及应用_IT/计算机_专业资料。acm模板/* SPFA 算法模板以及邻接表(Adjacency List)的构造 */ #include<iostream> #include<cmat...


spfa讲义

SPFA 算法求单源最短路的 SPFA 算法的全称是:Shortest Path Faster Algorithm。 SPFA 算法是西南交通大学段凡丁于 1994 年发表的. 从名字我们就可以看出,这种算法...


前向星_SPFA

spfa算法 12页 免费 前向星 6页 免费 前向星 SPFA 5页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


费用流SPFA

SPFA代码 2页 免费 完整spfa 1页 2下载券 关于SPFA算法 2页 免费喜欢此文档...[cnt_m+j+2]; // 逆边一定要记得加 } } bool spfa() { int i, u,...


图论 第四讲 经典算法

图的经典算法有 求单源最短路径的迪杰斯特拉算法,SPFA 算法, 求负权回路的 ...下面给出一种讲解。关键路径问题 利用 AOV 网络,对其进行拓扑排序能对工程中...


算法代码大全

[j]; } } ②.SPFA 算法(邻接链表)//SPFA 是个好东西啊,不仅仅可以用来求最短路,还可以它所提供 的类拓扑序进行 DP 实例:最优贸易 (1).货真价实的邻接...


省选算法总结

[b]=L++; 11 算法总结 By Jiangzh http://blog.csdn.net/jiangzh7 } bool spfa() { memset(h,0,sizeof(h)); memset(dist,0x3f,sizeof(dist)); ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com