9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

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算法详解_学科竞赛_高中教育_教育专区。SPFA 算法详解 适用范围: 给定的图存在负权边,这时类似 Dijkstra 等算法便没有了用武之地, 而 Bellman-Ford 算法的...
SPFA单源最短路算法讲解
SPFA单源最短路算法讲解_IT/计算机_专业资料。本文来源: http://www.cnblogs.com/zgmf_x20a/ Beetlebum 的 Blog 最短路径 之 SPFA 算法求最短路径的算法有许 ...
2 求含有负权边的图的单源最短路径——Bellman Ford算法与SPFA算法综合分析(下)
SPFA单源最短路算法讲解 4页 免费 求单源最短路-SPFA算法 11页 8财富值 求...求含有负权边的图的单源最短路径——Bellman Ford 算法与 SPFA 算法综合分析(...
1 求含有负权边的图的单源最短路径——Bellman Ford算法与SPFA算法综合分析(上)
1 求含有负权边的图的单源最短路径——Bellman Ford算法与SPFA算法综合分析(上...SPFA单源最短路算法讲解 4页 免费 求单源最短路-SPFA算法 11页 3下载券 求...
SPFA算法简介
SPFA算法简介_IT/计算机_专业资料。SPFA 算法简介 算法采用图的存储结构是邻接表...SPFA单源最短路算法讲解 4页 免费 SPFA 2页 免费 SPFA算法的优化及应用 37页...
SPFA算法
37页 免费 spfa讲义 10页 免费 SPFA算法 5页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
SPFA算法C语言版
SPFA算法C语言版_计算机软件及应用_IT/计算机_专业资料。#include<cstdio> using...SPFA算法的优化及应用 37页 1下载券 SPFA单源最短路算法讲解 4页 免费喜欢...
spfa算法(边集数组的介绍)
NOIP图的基础算法 76页 免费 SPFA单源最短路算法讲解 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
SPFA算法的优化及应用
37 - 第 2 页共 37 页 - 2009Thesis SPFA 的优化与应用 姜碧野 【正文】 SPFA 算法简介 1.1 SPFA 算法的基本实现下面,先介绍一下 SPFA 和 Bellman-Ford...
算法分析与设计
SPFA还有SLF, LLL,滚动数组等优化。 该算法的理论分析如下: 1,.初始化:将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0; 2.迭代求解: ...
更多相关标签:
spfa算法    spfa    a*算法    段凡丁    spfa算法pascal    spfa算法模板    spfa算法复杂度    多源最短路径算法spfa    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图