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

2009ThesisSPFA的优化与应用姜碧野
迭代求解的利器
--------SPFA算法的优化与应用

广东中山纪念中学姜碧野

【摘要】

SPFA算法,全称ShortestPathFasterAlgorithm,是Bellman-Ford算法的改进
版。该算法以三角不等式为基础，实现时借助队列或栈不断进行迭代以求得最优
解。具有效率高、实现简洁、扩展性强等优点。三角不等式的普适性及其类似搜
索的实现方式，使其应用并不只局限于图论中的最短路径，更可以在动态规划、
迭代法解方程中发挥出巨大的作用，解决一些非常规问题；还可根据具体问题进

行各种各样的优化。本文将对其进行全面的分析、测试和深入的讨论。

【关键词】迭代SPFA深度优先搜索最优性动态规划状态转移方程

--
2009ThesisSPFA的优化与应用姜碧野

【目录】

SPFA算法简介............................................................................................3

1.1SPFA算法的基本实现....................................................................3

1.2活学活用：SPFA的深度优先实现及其优化...............................5

1.2.1:基于Dfs的SPFA的基本原理.................................................5

1.2.2:基于Dfs的SPFA的相关优化.................................................7

1.3SPFA算法实际效果测试及比较....................................................8

*1.4Johnson算法介绍........................................................................12

2.SPFA算法在实际应用中的优化...........................................................13

2.1如何使用SPFA快速查找负(正)环...............................................13

2.2注意对无用状态的裁剪...............................................................17

3.SPFA算法的应用..................................................................................19

3.1差分约束系统...............................................................................19

3.2在一类状态转移阶段性不明显的动态规划中的应用...............20

3.3探讨SPFA在解方程中的应用......................................................23

3.4一类状态转移存在“后效性”的动态规划中的应用...................28

5附录........................................................................................................33

5.1例题原题.......................................................................................33

5.2源程序&例题测试数据................................................................37

6.参考文献...............................................................................................37

7.鸣谢....................................................