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

《算法合集之《SPFA算法的优化及应用》.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2009ThesisSPFA的优化与应用姜碧野迭代求解的利器--------SPFA算法的优化与应用广东中山纪念中学姜碧野【摘要】SPFA算法,全称ShortestPathFasterAlgorithm,是Bellman-Ford算法的改进版。该算法以三角不等式为基础，实现时借助队列或栈不断进行迭代以求得最优解。具有效率高、实现简洁、扩展性强等优点。三角不等式的普适性及其类似搜索的实现方式，使其应用并不只局限于图论中的最短路径，更可以在动态规划、迭代法解方程中发挥出巨大的作用，解决一些非常规问题；还可根据具体问题进行各种各样的优化。本文将对其进行全面的分析、测试和深

2、入的讨论。【关键词】迭代SPFA深度优先搜索最优性动态规划状态转移方程-第1页共37页-2009ThesisSPFA的优化与应用姜碧野【目录】SPFA算法简介............................................................................................31.1SPFA算法的基本实现....................................................................31.2活学活用：SPFA的深度优先实现及其优化........

3、.......................51.2.1:基于Dfs的SPFA的基本原理.................................................51.2.2:基于Dfs的SPFA的相关优化.................................................71.3SPFA算法实际效果测试及比较....................................................8*1.4Johnson算法介绍..................................

4、......................................122.SPFA算法在实际应用中的优化...........................................................132.1如何使用SPFA快速查找负(正)环...............................................132.2注意对无用状态的裁剪...............................................................173.SPFA算法的应用..........

5、........................................................................193.1差分约束系统...............................................................................193.2在一类状态转移阶段性不明显的动态规划中的应用...............203.3探讨SPFA在解方程中的应用......................................................233.4一类状态

6、转移存在“后效性”的动态规划中的应用...................285附录........................................................................................................335.1例题原题.......................................................................................335.2源程序&例题测试数据.............................

7、...................................376.参考文献...............................................................................................377.鸣谢........................................................................................................37-第2页共37页-2009ThesisSPFA的优化与应用姜碧野【正