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

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 实际上是 Bellman-Ford 基础上的队列优化 SPFA(G,w,s) 1. INITIALIZE-SINGLE-SOURCE(G,s) 2. INITIALIZE-QUEUE(Q) 3. ENQUEUE(Q,s...
SPFA算法C语言版
SPFA算法C语言版_计算机软件及应用_IT/计算机_专业资料。#include<cstdio> using...SPFA算法的优化及应用 37页 1下载券 SPFA单源最短路算法讲解 4页 免费喜欢...
SPFA算法的优化及应用
37 - 第 2 页共 37 页 - 2009Thesis SPFA 的优化与应用 姜碧野 【正文】 SPFA 算法简介 1.1 SPFA 算法的基本实现下面,先介绍一下 SPFA 和 Bellman-Ford...
spfa讲义
SPFA 算法求单源最短路的 SPFA 算法的全称是:Shortest Path Faster Algorithm。...SPFA单源最短路算法讲解 4页 免费 SPFA算法的优化及应用 37页 1下载券 SPFA...
邻接表的构造以及SPFA模板
邻接表的构造以及SPFA模板_计算机软件及应用_IT/计算机_专业资料。acm模板/* SPFA 算法模板以及邻接表(Adjacency List)的构造 */ #include<iostream> #include<cmat...
spfa理论成立
这个算法,简单的说就是队列优化的 bellman-ford,利用了每个点不会更新次数 太多...SPFA单源最短路算法讲解 4页 免费 Spfa&二分 暂无评价 5页 免费 喜欢...
...—Bellman Ford算法与SPFA算法综合分析(上)
1 求含有负权边的图的单源最短路径——Bellman Ford算法与SPFA算法综合分析(上...SPFA单源最短路算法讲解 4页 免费 求单源最短路-SPFA算法 11页 3下载券 求...
算法分析与设计
SPFA还有SLF, LLL,滚动数组等优化。 该算法的理论分析如下: 1,.初始化:将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0; 2.迭代求解: ...
图论 第四讲 经典算法
图的经典算法有 求单源最短路径的迪杰斯特拉算法,SPFA 算法, 求负权回路的 ...下面给出一种讲解。关键路径问题 利用 AOV 网络,对其进行拓扑排序能对工程中...
最小费用最大流-SPFA增广
最小费用最大流-SPFA增广_IT/计算机_专业资料。最小费用最大流网络流的基本...(i,j): + - 因此,确定最小费用最大流的具体算法如下: (1)从零流开始,...
更多相关标签:
spfa算法 | spfa | a*算法 | 段凡丁 | spfa算法模板 | spfa算法复杂度 | spfa算法 cnblog | spfa算法模版 |