2009Thesis SPFA的优化与应用 姜碧野

迭代求解的利器

--------SPFA算法的优化与应用

广东中山纪念中学 姜碧野

【摘要】

SPFA算法,全称Shortest Path Faster Algorithm,是Bellman-Ford算法的改进

版。该算法以三角不等式为基础，实现时借助队列或栈不断进行迭代以求得最优解。具有效率高、实现简洁、扩展性强等优点。三角不等式的普适性及其类似搜索的实现方式，使其应用并不只局限于图论中的最短路径，更可以在动态规划、迭代法解方程中发挥出巨大的作用，解决一些非常规问题；还可根据具体问题进行各种各样的优化。本文将对其进行全面的分析、测试和深入的讨论。

【关键词】迭代 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 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.鸣谢 ................................................................................................. 37

- 第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求解。在下文中将看到相关的应用。

有了三角不等式后，SPFA也即Bellman-Ford的核心算法也就登场了。也就是著名的松弛操作。

首先令f(u)为节点的u的当前最优最短路，并赋初值f(s)=0,f(u)=+∞(u≠s) 然后对每条不满足三角不等式的边，我们都把其目标节点重新赋值。

即：对于(u,v)∈E Relax(u,v){

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) >=d(s,u)+w(u,v) >=d(s,v)

而在没有负环的情况下，每个f(u)肯定是单调不增的，这也证明了该算法肯

定会结束的。更进一步，如果我们采用Bellman-Ford的计算方式：

For i=1 to n-1

For (u,v) ∈E

Relax(u,v)；

便可以在N*M的时间中算出最短路径，因为最短路径的边数最多为N-1,而

由数学归纳法知：当外循环为第I次时，我们算出了长度为I的最短路，而经过第I+1次的循环，必然可以得出长度为I+1的最短路。

不存在负环时，最短路经过的边数显然不超过N-1，这也告诉我们第N次迭代如果发现可以继续更新则必然存在负环。

而事实上，Bellman-Ford的实际效率是很低的，因为有很多不必要的操作。考虑图为一条链时的情况：

-1 -1 -1 -1 S A1 .......

AnT 如果直接使用Bellman-Ford，则每次迭代实际上只能更新一个节点，其他的循环都是无效的。因此可以发现只有在上一次迭代中被更新的节点才会对当前的

- 第4页共37页 -