当前位置：文档之家 › 算法合集之《SPFA算法的优化及应用》

算法合集之《SPFA算法的优化及应用》

  • 格式：pdf
  • 大小：525.05 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

算法合集之《SPFA算法的优化及应用》

算法合集之《SPFA算法的优化及应用》

更新时只需考虑点对间关系(最短路迭代算法)
利用标号法则使用贪心思想再优化
每个节点只扩展一次 (标号法)
三者的本质都是统一的，但随着算法
的优化适用面逐步缩窄 优化算法是好的，但如果没有对算法 有着深刻的认识，忽略了算法的适用条件， 思维的定势很容易使我们得出错误算法。
总结
在对Bellman-Ford算法的合理优化中， 诞生了高效的SPFA算法。
在查找负环中，抛开了传统的实现方式， 我们得出一种崭新的架构使效率大大提高
在动态规划中，摆脱了思维定势的影响， 我们才得出正确的解法。 SPFA并不是一个死板的经典算法，我们 只有灵活运用才能发挥其应有的奇效。 灵活
F[ ]= 3 5 4
4 G’[ ]=
F[ ]=MAX(G[ ],G’[ ])
之后G[ ]得出最优解2
特点: 赋值时考虑的是一个整体，即需要在所有与当 前节点关联的状态中取最值，保证了合法性。 G[ ]被更新时F[ ]还要重新考虑G’[ ]。
算法正确吗？让我们继续分析。
性质1：该算法结束时求得的解为正确解。 证明：该结论显然，算法结束意味各个方程均成立 性质2：该算法一定会结束。 证明： 把状态按照其最终值的大小分层，则可以发现 当前K层确定时，对于第K+1层有： 1.G[ ]可以从前K+1层取得最小值。 2.F[ ]的最大值只能从前K+1层取，否则其最终值
开始时 A无法 移动
此时B不能再向左移动 而A可以逐步摘下3棵树的所有苹果
之后B一直不动， A无法得到任何苹果
问题分析: 经典的博弈模型，数据规模比较小，考虑动态规划
F[X,Y,K]表示轮到A行动， A的位置为X，B的位置为Y， 苹果树状态为K(使用状态压缩的4位4进制表示）时 A最多获得多少苹果。 G[X,Y,K]类似表示轮到B行动时，A最少获得的苹果数。 状态数为30*30*256*2 ≈500000 可以承受 转移方程也简单，直接枚举5种行动 F[X,Y,K]=Max(G[X’,Y’,K’]+Apple)

一种SPF计算调度算法的设计与实现

一种SPF计算调度算法的设计与实现

一种SPF计算调度算法的设计与实现
平骁卓;葛宝忠
【期刊名称】《微计算机信息》
【年(卷),期】2005(000)024
【摘要】传统的OSPF路由协议实现满足SPF计算条件,就执行SPF计算:频繁的计算消耗大量宝贵的系统资源,还使计算得出的路由表稳定性较差.设计并实现对SPF计算的调度算法,保证两次SPF计算满足合理的间隔,提高单次SPF计算的效率,减缓了路由表更新的速率,提高了路由稳定性,节约了大量的系统开销.在T比特路由器平台上进行了测试验证,结果表明该算法达到设计目的.分析指出该算法也很好的满足了SPF计算的可靠性和健壮性要求.
【总页数】4页(P61-63,146)
【作者】平骁卓;葛宝忠
【作者单位】450002,郑州国家数字交换系统工程技术研究中心;450002,郑州国家数字交换系统工程技术研究中心
【正文语种】中文
【中图分类】TP393.17
【相关文献】
1.一种改进的进程调度算法在机顶盒上的设计与实现 [J], 王铭伟;吕华
2.ASPFQ:一种简单公平的队列调度算法 [J], 时培昕;柴洪杰;雷振明
3.一种多用户MapReduce集群的作业调度算法的设计与实现 [J], 王凯;吴泉源;
杨树强
4.一种SPF计算调度算法的设计与实现 [J], 平骁卓;葛宝忠
5.一种多核混合分区调度算法设计与实现 [J], 郝继锋;虞保忠;周霆;徐晓光
因版权原因，仅展示原文概要，查看原文内容请购买。

SPFA算法

SPFA算法

让我们结合一道题目来进行探讨
苹果争夺战 两个人A,B在一个5*6的矩阵里抢夺苹果。矩阵包含空地，4棵 苹果树和障碍物，每个苹果树上有3个苹果。A先行动，然后两人轮 流操作，每一回合每人可以向四周移动一格或停留在一棵苹果树下， 如果苹果树非空可以摘下一个苹果。 两人不能移动到矩阵外，障碍物上或是对方的位置，且两人绝 顶聪明。 问A最多可以抢到多少个苹果。
SPFA的核心正是松弛操作：
Relax(u,v){
If （F(v)>F(u)+W_Cost(u,v)） F(v)=F(u)+W_Cost (u,v);
}
但松弛操作直接得出的Bellman-Ford算法效率低下
For Time=1 to N For (u,v)∈E Relax(u,v)
S A1
.......
我们再从另一个角度来分析DIJ和spfa
Dij的思想可以从另一个角度来阐述：一个
点的最短路必定从另一个点的最短路推导 出，而另一个点的最短路必定<这个点的最 短路，因此我们可以DP，但是因为存在环， 所以就只能从最短路最小的那个开始推， 所以只要满足求的是最短路，都可以用DIJ。
我们再从另一个角度来分析DIJ和spfa
类似于在负权图上使用Dijikstra
因此标号法并不适用
思路二：参考负权图上求最短路的思想
通过局部的较优值一步步迭代得到最优解
假设当前解为：
G[ ]= 4 5
F[ ]= 3 5
之后G[ ]得出最优解4
问题所在：F[ ]和G[ ]的最优化目标不同
两种常规解法都失败了，我们需要从新的角度来思考 猜想： 能否越过状态间纷繁复杂的转移关系 直接考虑最终状态呢？
当某边三角不等式不成立时，用松弛操作调整之。

最短路径SPFAP3371【模板】单源最短路径（弱化版）

最短路径SPFAP3371【模板】单源最短路径（弱化版）

最短路径SPFAP3371【模板】单源最短路径（弱化版）SPFA算法：SPFA 算法是的队列优化算法的别称，通常⽤于求含负权边的单源最短路径，以及判负权环。

SPFA 最坏情况下复杂度和朴素Bellman-Ford 相同，为 O(VE)。

SPFA和Dijkstra不同的是：Dijkstra 是从⼀个点的所有出边中找到⼀个最短出边，⽤它来继续更新下边的点SPFA 是⽤⼀个点的所有出边都更新它下⾯的点更新之前把这个点存进队列更新时把他拿出来，再把更新的出边终点（未⼊队的）⼊队⼀直不断更新，直到队列为空队列⾥存的是点（下⾯有详细解释，在链式前向星以后）head[---] 这⾥⼤⼩根据点数决定记录存边的历史，存的是i点的最后⼀条出边（它经历了不断更新）vis[---] 判断是否已存⼊队列dis[---] 从起点开始到当前点的最短路径num_edge 表⽰边的编号这⾥要⽤链式前向星存图：//以下为链式前向星存图void addedge(int from,int to,int dis) //存储每⼀条边：起点，终点，长度{num_edge++; //新建⼀条边edge[num_edge].next=head[from]; //上⼀条出边edge[num_edge].to=to;edge[num_edge].dis=dis;head[from]=num_edge; //记录最后⼀条出边}这⾥edge[1]=0，因为它是顶点1的第⼀条出边edge[2]=1，edge[3]=2，edge[5]=0，因为它是顶点5 的第⼀条出边edge[7]=5SPFA默认起点是1⽤到1就把它弹出再⽤6更新5⼊队再⽤3更新直到队列为空【代码】：#include<bits/stdc++.h>#include<queue>using namespace std;const int inf=2147483647;int n,m,s;int dis[10008],vis[10008],head[10008],num_edge;struct Edge{int next,to,dis;}edge[500008]; //⼤⼩由边数决定// to ⽬标点// dis 权值// next 该点的上⼀条出边queue<int>q;//以下为链式前向星存图void addedge(int from,int to,int dis) //存储每⼀条边：起点，终点，长度{num_edge++; //新建⼀条边edge[num_edge].next=head[from]; //上⼀条出边edge[num_edge].to=to;edge[num_edge].dis=dis;head[from]=num_edge; //记录最后⼀条出边}void spfa(){for(int i=1;i<=n;i++){dis[i]=inf; //初始化最⼤值vis[i]=0; //都不⼊队}dis[s]=0;vis[s]=1;q.push(s); //把起点S⼊队while(!q.empty()){int u=q.front(); //当前起点q.pop(); //⽤就弹出vis[u]=0; //弹出后记录为不在队列for(int i=head[u];i;i=edge[i].next) //遍历起点的所有出边{int v=edge[i].to; //当前终点if(dis[v]>dis[u]+edge[i].dis)//如果【起点到当前终点的距离】>【起点到当前起点的距离＋当前距离与当前终点距离】 //那就更新为更⼩距离{dis[v]=dis[u]+edge[i].dis;if(!vis[v]) //未⼊队的当前终点⼊队 {q.push(v);vis[v]=1;}}}}}int main(){scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);}spfa();for(int i=1;i<=n;i++){if(i==s) printf("0 ");else printf("%d ",dis[i]);}return0;}。

FOA优化极限学习机算法及模型应用研究

FOA优化极限学习机算法及模型应用研究

FOA优化极限学习机算法及模型应用研究
潘华贤
【期刊名称】《微型电脑应用》
【年(卷),期】2024(40)3
【摘要】传统极限学习机算法输入权重和单元偏置是随机确定的,这会导致算法性能不高,因而采用果蝇优化算法进行优化。

分析了果蝇优化算法的流程,并和遗传算法、粒子群算法进行对比,通过求解Schaffer函数最优化问题验证了果蝇优化算法具有良好的优化性能。

在此基础上,将果蝇优化算法优化极限学习机,提出改进的极限学习机算法。

将改进极限学习机算法和极限学习机算法应用于化工企业竞争力预测中,结果表明,改进极限学习机算法对化工企业竞争力预测的准确率明显高于极限学习机算法,同时运行时间相差非常小。

FOA优化极限学习机模型对其他预测问题的解决提供了参考。

【总页数】4页(P108-111)
【作者】潘华贤
【作者单位】西安财经大学行知学院
【正文语种】中文
【中图分类】TP18
【相关文献】
1.基于蚁群算法和极限学习机的舰船电子装备备件优化模型
2.基于相空间重构和遗传算法优化的极限学习机模型预测基坑变形时序混沌特性
3.基于改进SSA算法优
化极限学习机模型的土壤供肥量预测4.基于小波包分解-非洲秃鹫优化算法-深度极限学习机的水文预报模型及其应用5.基于混沌多目标蚁狮优化算法和核极限学习机的冲击性负荷预测模型
因版权原因，仅展示原文概要，查看原文内容请购买。

spfa算法

spfa算法
对于图中的每个顶点v∈ ，都设置一个属性d[v]，描述从源点 到v的最 对于图中的每个顶点 ∈V，都设置一个属性 ，描述从源点s到 的最 短路径上权值的上界，称为最短路径估计。 代表S到 的当前最短路径 短路径上权值的上界，称为最短路径估计。pre[v]代表 到v的当前最短路径 代表 中v点之前的一个点的编号 我们用下面的过程来对最短路径估计和前趋进行 点之前的一个点的编号,我们用下面的过程来对最短路径估计和前趋进行 点之前的一个点的编号 初始化。（ 。（Θ(V)时间）。经过初始化以后，对所有 ∈V，pre[v]=NULL，对 时间）。经过初始化以后， 初始化。（ 时间）。经过初始化以后 对所有v∈ ， ， v∈V-{s}，有d[s]=0以及 以及d[v]=∞。 ∈ ， 以及 。
队首元素d点出队，对以 为起始点的所有边的终点依次进行松弛操作 为起始点的所有边的终点依次进行松弛操作（ 队首元素 点出队，对以d为起始点的所有边的终点依次进行松弛操作（此 点出队 处只有g这个点），此时路径表格状态为 这个点），此时路径表格状态为： 处只有 这个点），此时路径表格状态为：
a d[i] 0
a d[i] 0
b
c
d
e
f
g ∞
24 8
15 30 ∞
在最短路径表中， 的最短路径估值也变小了 的最短路径估值也变小了， 在队列中不存在 因此e也要 在队列中不存在， 在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此 也要 入队，此时队列中的元素为c， ， 入队，此时队列中的元素为 ，d，e 队首元素c点出队，对以 为起始点的所有边的终点依次进行松弛操作 为起始点的所有边的终点依次进行松弛操作（ 队首元素 点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处 点出队 两个点），此时路径表格状态为： 有e,f两个点），此时路径表格状态为： 两个点），此时路径表格状态为

算法合集之《SPFA算法的优化及应用》

算法合集之《SPFA算法的优化及应用》SPFA算法即最短路径快速算法（Shortest Path Faster Algorithm）。

它是Bellman-Ford算法的一种优化算法，主要用于求解单源最短路径问题，即从一个节点出发，求解到达其他节点的最短路径。

SPFA算法的基本思想是利用队列进行松弛操作，不断更新节点的距离值，直到所有节点的距离值不再更新。

与普通的队列实现不同，SPFA算法通过维护一个优化队列，将已经被更新的节点推入队列的前部，这样可以提高算法的效率。

SPFA算法的优化主要体现在以下几个方面：1.队列优化：SPFA算法通过优化队列的维护顺序，将已经被更新的节点推入队列的前部。

这样，被更新的节点会尽快参与下一次的松弛操作，从而减少了不必要的松弛操作，提高了算法的效率。

2.标记优化：SPFA算法引入了一个标记数组，用于标记节点是否在队列中。

只有当节点的距离值发生改变时，才会将节点推入队列，并将其标记为在队列中。

这样可以避免重复将相同节点推入队列，减少了不必要的操作。

3.最短路径优化：SPFA算法在每次松弛操作时，会检查节点的距离值是否发生了改变。

如果节点的距离值没有发生改变，则说明该节点的最短路径已经确定，不需要再进行松弛操作。

这样可以减少不必要的松弛操作，提高算法的效率。

SPFA算法的应用非常广泛，主要应用在网络最短路径问题、有向图中的单源最短路径问题等。

具体应用如下所示：1.网络路由：SPFA算法可以用于求解网络中的最短路径，用于确定数据包的传输路径，从而提高网络的传输效率。

2.电力传输：SPFA算法可以用于求解电力网络中的最短路径，用于确定电力传输的路径，从而提高电力传输的效率。

3.交通规划：SPFA算法可以用于求解交通网络中的最短路径，用于规划最短的驾驶路线，从而减少交通拥堵，提高交通的效率。

总之，SPFA算法通过队列优化、标记优化以及最短路径优化，提高了算法的效率，使得求解最短路径问题更加快速和高效。

SOA的寻优计算教程(MATLAB优化算法案例分析与应用PPT课件)人群搜索算法的函数优化

1.4 不确定性行为
根据介值定理，在连续搜索空间，极值点附近存在一个邻域；该邻域 内的点的目标函数值正比于该点到极值点的距离。因此可做如下假设： 较优解的周围可能存在更优的解，最优解可能存在于较优解的邻域内。 根据解的优劣有必要采取“聚焦”搜索；也就是，当搜寻者所处位置较 优时，应该在较小邻域内搜索；当搜寻者所处位置较差时，应该在较大 邻域内搜索。
0.1 0.09 0.08 0.07 0.06 0.05 0.04 0.03 0.02 0.01
0 0
适应度
适 应 度 曲 线 终 止 代 数 ＝ 100
SOA PSO
20
40
60
80
100
进化代数
图22-3 综合比较曲线
MATLAB优化算法案例分析与应用
•4 基于人群搜索算法的函数优化
（3）函数Rastrigin:
不确定性，是人类社会现象的基本属性。人类的认知过程是通过语言 和思维进行的，人类依托语言进行思维；自然语言是人类的思维基础， 是人类智能的体现。模糊系统正是基于模拟人类利用自然语言来描述
复杂系统的需要提出的，模糊控制规则就是人类控制行为的语言模型 ；人类思维具有普遍模糊性的现象表明，模糊逻辑在描述人类思维方面 扮演了重要的角色。
16 14 12 10
8 6 4 2 0
0
适应度
适 应 度 曲 线 终 止 代 数 ＝ 100
SOA PSO
20
40
60
80
100
进化代数
图22-3 综合比较曲线
MATLAB优化算法案例分析与应用
•4 基于人群搜索算法的函数优化
综合上述三种典型函数Sphere，Schaffer和Rastrigin，经 PSO和SOA算法的对比研究可知，人群搜索算法具有鲁棒 性好，算法较快的收敛性，算法求解最优值避免早熟等现 象的发生，因此，人群算法完成函数优化分析具有收敛精 度高等特点。

SPFA算法

SPFA 算法(也适合求最长路径)求单源最短路的SPF A 算法的全称是：Shortest Path Faster Algorithm 。

从名字我们就可以看出，这种算法在效率上一定有过人之处。

很多时候，给定的图存在负权边，这时类似Dijkstra 等算法便没有了用武之地，而Bellman-Ford 算法的复杂度又过高，SPF A 算法便派上用场了。

简洁起见，我们约定有向加权图G 不存在负权回路，即最短路径一定存在。

当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。

和上文一样，我们用数组d 记录每个结点的最短路径估计值，而且用邻接表来存储图G 。

我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u ，并且用u 点当前的最短路径估计值对离开u 点所指向的结点v 进行松弛操作（即不断选优调整），如果v 点的最短路径估计值有所调整，且v 点不在当前的队列中，就将v 点放入队尾（如果v 点已在队列中，则更新调整。

注意点v 可能会多次进入队列）。

这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

(可以采用循环数组队列)定理3 只要最短路径存在，上述SPFA 算法必定能求出最小值。

证明：每次将点放入队尾，都是经过松弛操作达到的。

换言之，每次的优化将会有某个点v 的最短路径估计值d[v ]变小。

所以算法的执行会使d 越来越小。

由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。

因此，算法不会无限执行下去，随着d 值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。

（证毕）刚才我们只是笼统地说SPF A 算法在效率上有过人之处，那么到底它的复杂度是怎样的？定理4 在平均情况下，SPFA 算法的期望时间复杂度为O(E)。

证明：上述算法每次取出队首结点u ，并访问u 的所有临结点的复杂度为O(d)，其中d 为点u 的出度。

平滑改进A算法在无人机航迹规划中的应用

平滑改进A*算法在无人机航迹规划中的应用作者：储泽楠赵凯宋倍倍来源：《计算机时代》2020年第02期摘要：传统的A*算法易于陷入局部极小，搜索速度較慢，规划的路径有较多折线。

文章对传统A*算法进行了两个改进，并将其应用于无人机航迹规划。

一是在代价函数中加入无人机的转向代价估计，稳定其飞行方向;二是采用后处理方法对航迹点进行拟合，获得平滑的最短路径曲线。

为保证拟合后的路径不会出现较大波动，拟合过程没有使用所有的航迹点，而是在一定的误差允许范围内选取特征点进行拟合。

改进算法的有效性通过仿真和实验予以验证。

关键词： A*算法; 曲线拟合; 无人机; 后处理中图分类号：TP399 文献标识码：A 文章编号：1006-8228（2020）02-54-04Application of smooth improved A-star algorithm in UAV flight path planningChu Zenan1， Zhao Kai1， Song Beibei2（1.Anyang Institute of Technology， 2.Anyang Quality and Technical Supervision，Inspection and Testing Center， Anyang， Henan 455000， China）Abstract： Traditional A-star algorithm spends much time on searching optimal solution， and is easy to fall into local minima. Moreover， the planned path contains many polygonal lines. In this paper， two improvements are made to the traditional A-star algorithm， and it is applied to the pathplanning of UAV. One is to add the UAV steering cost estimation to the distance cost function to stabilize its flight direction; the other is to use the post processing method to fit the track points to obtain the smooth shortest path curve. In order to ensure that the fitted path will not fluctuate greatly， the fitting process does not use all the track points， but selects the feature points for fitting within a certain range of allowable error. The effectiveness of the improved algorithm is verified by simulation and experiment.Key words： A-star algorithm; curve fitting; unmanned aerial vehicle; post processing method 0 引言A*算法结构简单，易于执行，受到了人们的广泛关注。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

- 第 2 页共 37 页 -
2009Thesis
【正文】
SPFA 的优化与应用
姜碧野
SPFA 算法简介
1.1 SPFA 算法的基本实现
下面，先介绍一下 SPFA 和 Bellman-Ford 算法的原理和适用条件。 首先一个很重要的性质便是三角不等式。 设 G=(V,E)为一带权有向图，其权函数 w:EÆR 为边到实型权值的映射，s 为源点，对于任意点 t,d(s,t)为 s 到 t 的最短路。 则对于所有边(u,v)∈E 有 d(s,v)<=d(s,u)+w(u,v)。 令 d(s,s)=0，这一不等式为 d(s,t)是 s 到 t 的最短路的充要条件。 这一性质很容易理解。我们也很容易将其推广。 设 G=(V,E)为一带权有向图，d(u)为状态(顶点)u 的最优值，权函数 w:EÆ自定 义集合。则对于所有边(u,v)∈E 有 d(u)+w(u,v)不优于 d(v). 注:这里的“+”可以是延伸为任意形式的运算表达式。 更进一步，我们并不一定将不等式限定在“最优性”这一框架中，而可根据 具体题目要求制定自己的判断。推广后的三角不等式将不再拘束于最短路问题， 有着更加广泛的适用空间。只要我们根据题目构造出状态间的权函数和优劣判断 标准，在大部分情况下我们都可以使用 SPFA 求解。在下文中将看到相关的应用。
3. SPFA算法的应用.................................................................................. 19 3.1 差分约束系统 ............................................................................... 19 3.2 在一类状态转移阶段性不明显的动态规划中的应用............... 20 3.3 探讨SPFA在解方程中的应用...................................................... 23 3.4 一类状态转移存在“后效性”的动态规划中的应用 ................... 28
- 第 6 页共 37 页 -源自2009ThesisSPFA 的优化与应用
姜碧野
1.2.2:基于 Dfs 的 SPFA 的相关优化 Dfs 的实现方式虽然暂时无法取得好的效果，但我们并不应该就此放弃，Dfs
相对 Bfs 灵活的架构必能给予我们广阔的优化空间。 首先，一个很自然的想法便是改变搜索顺序，即把边按照一定的规则排序，
If f(v)>f(u)+w(u,v) f(v)=f(u)+w(u,v);
- 第 3 页共 37 页 -
2009Thesis
SPFA 的优化与应用
姜碧野
} 松弛操作的本质正是：不断寻找当前状态与目标状态间的矛盾并调整，直到 找不到矛盾时即达到最优状态。 由松弛操作，我们又可以得出一些有用的推论： 上界性质&收敛性质: 在算法过程中，对于所有 u,都有 f(u)>=d(s,u)。因此一旦 f(u)达到 d(s,u), f(u) 将不会再改变。这一点很容易理解，因为由于归纳法可知，只要原来满足 f(u)>=d(s,u),那么执行松弛操作后，显然有： f(v)=f(u)+w(u,v)
1.2.1:基于 Dfs 的 SPFA 的基本原理 在上面的介绍的算法中，我们用一个循环队列来存储需要继续迭代的节点，
实现时使用类似广度优先搜索的方式。那么我们是否可以使用搜索的另一利器： 深度优先呢？
回忆之前的算法，由于采用广度优先的思想，每当我们扩展出一个新的节点，
1 证明见 2006 余远铭论文《最短路算法及其应用》 - 第 5 页共 37 页 -
5 附录 ........................................................................................................ 33 5.1 例题原题 ....................................................................................... 33 5.2 源程序&例题测试数据................................................................ 37
6.参考文献 ............................................................................................... 37 7.鸣谢 ........................................................................................................ 37
- 第 4 页共 37 页 -
2009Thesis
SPFA 的优化与应用
姜碧野
迭代有用，SPFA 正是利用了这一点，采用了队列进行优化。其核心是只保存当
前有用状态，每次将被更新的节点放入队列中等待扩展，而未被更新的则不予考
虑。而由于任意时刻队列中最多只有 N 个元素，所以使用循环队列。具体算法伪
代码如下：
2.SPFA算法在实际应用中的优化........................................................... 13 2.1 如何使用SPFA快速查找负(正)环 ............................................... 13 2.2 注意对无用状态的裁剪 ............................................................... 17
【关键词】迭代 SPFA 深度优先搜索 最优性 动态规划 状态转移 方程
- 第 1 页共 37 页 -
2009Thesis
SPFA 的优化与应用
姜碧野
【目录】
SPFA算法简介............................................................................................ 3 1.1 SPFA算法的基本实现.................................................................... 3 1.2 活学活用：SPFA的深度优先实现及其优化 ............................... 5 1.2.1:基于Dfs的SPFA的基本原理................................................. 5 1.2.2:基于Dfs的SPFA的相关优化................................................. 7 1.3 SPFA算法实际效果测试及比较.................................................... 8 *1.4 Johnson算法介绍........................................................................ 12
2009Thesis
SPFA 的优化与应用
姜碧野
总是把它放到队列的末尾，其缺点是中断了迭代的连续性。而实际上如果采用深 度优先的思想，我们可以直接从这个新节点继续往下扩展。于是算法的实现方式 可以改成不断从新节点往下递归进行求解。
而对于负环的判断则显得更为简单，因为假如存在负环a1->a2->….ak->a1，
Halt;
} } } Out_data; } 在一般情况，SPFA的效率很高，可以证明1SPFA的期望复杂度为O(KM)，K<2。
但由于证明还不够严谨且适用性不广(存在针对性数据)，在此不再赘述。但将会
在随后的测试中用实际数据来验证SPFA的高效性。
1.2 活学活用：SPFA 的深度优先实现及其优化
} 两种算法的原理相同，相对 Bellman-Ford 的优化也是殊途同归的。其精髓都 在于只保存有用的状态。 那么，SPFA 的这种实现效率如何呢？在随后的初步尝试中，笔者发现，在一 些拓扑关系比较强的时候，广度会有很大的优势。Dfs 往往由于不断盲目地迭代 而耗费了太多时间甚至远远超过时间的限制。 因此在下文中，笔者将结合深度优先搜索的特点，尝试对其进行优化。
不存在负环时，最短路经过的边数显然不超过 N-1，这也告诉我们第 N 次迭 代如果发现可以继续更新则必然存在负环。
而事实上，Bellman-Ford 的实际效率是很低的，因为有很多不必要的操作。 考虑图为一条链时的情况：
-1
S
-1
A1
-1
......
-1
An
T
如果直接使用 Bellman-Ford，则每次迭代实际上只能更新一个节点，其他的 循环都是无效的。因此可以发现只有在上一次迭代中被更新的节点才会对当前的
2009Thesis
SPFA 的优化与应用
姜碧野
迭代求解的利器
--------SPFA 算法的优化与应用
广东中山纪念中学 姜碧野
【摘要】
SPFA 算法,全称 Shortest Path Faster Algorithm,是 Bellman-Ford 算法的改进 版。该算法以三角不等式为基础，实现时借助队列或栈不断进行迭代以求得最优 解。具有效率高、实现简洁、扩展性强等优点。三角不等式的普适性及其类似搜 索的实现方式，使其应用并不只局限于图论中的最短路径，更可以在动态规划、 迭代法解方程中发挥出巨大的作用，解决一些非常规问题；还可根据具体问题进 行各种各样的优化。本文将对其进行全面的分析、测试和深入的讨论。