当前位置:首页 >> 学科竞赛 >>

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/计算机_专业资料。acm模板/* SPFA 算法模板以及邻接表(Adjacency List)的构造 */ #include<iostream> #include<cmat...
算法学习:图论之SPFA算法,Bellman-Ford与差分约束系统
算法学习:图论之SPFA算法,Bellman-Ford与差分约束系统_计算机软件及应用_IT/计算机...POJ 1275 Cashier Employment 出纳员的雇佣 黑书上有详细讲解 POJ 1364 King ...
...—Bellman Ford算法与SPFA算法综合分析(上)
1 求含有负权边的图的单源最短路径——Bellman Ford算法与SPFA算法综合分析(上...SPFA单源最短路算法讲解 4页 免费 求单源最短路-SPFA算法 11页 3下载券 求...
前向星_SPFA
spfa算法 12页 免费 前向星 6页 免费 前向星 SPFA 5页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
最小费用最大流-SPFA增广
最小费用最大流-SPFA增广_IT/计算机_专业资料。最小费用最大流网络流的基本...(i,j): + - 因此,确定最小费用最大流的具体算法如下: (1)从零流开始,...
算法分析与设计
SPFA还有SLF, LLL,滚动数组等优化。 该算法的理论分析如下: 1,.初始化:将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0; 2.迭代求解: ...
图论 第四讲 经典算法
图的经典算法有 求单源最短路径的迪杰斯特拉算法,SPFA 算法, 求负权回路的 ...下面给出一种讲解。关键路径问题 利用 AOV 网络,对其进行拓扑排序能对工程中...
费用流SPFA
SPFA代码 2页 免费 完整spfa 1页 2下载券 关于SPFA算法 2页 免费喜欢此文档...[cnt_m+j+2]; // 逆边一定要记得加 } } bool spfa() { int i, u,...
NOIP算法整理_图文
(s,t); end; procedure spfa(s:longint); var i,j,now,sum:longint; NOIP 算法总结 30 山东省广饶一中 杨庆礼 begin fillchar(d,sizeof(d),0); ...
ACMer需要掌握的算法
>Spfa 算法 (稠密带负权图中 SPFA 的效率并不如 Bellman-Ford 高) 全源最短路弗洛伊德算法 Floyd 全源最短路 Johnson 算法 次短路径 第 k 短路径 差分约束...
更多相关标签:
spfa算法 | spfa | a*算法 | 段凡丁 | spfa算法 加权无向图 | spfa算法优化 | spfa算法模板 | spfa算法最小费用流 |