2009Thesis SPFA的优化与应用 姜碧野
迭代有用，SPFA正是利用了这一点，采用了队列进行优化。其核心是只保存当前有用状态，每次将被更新的节点放入队列中等待扩展，而未被更新的则不予考虑。而由于任意时刻队列中最多只有N个元素，所以使用循环队列。具体算法伪代码如下：
Program SPFA{ Init_graph
Push_Queue(s); While head≠tail{ x=Pop_Queue; For(x,v) ∈E
If f(v)>f(x)+w(x,v){ f(v)=f(x)+w(x,v)
if v not in queue Push_Queue (v); If (v has been in Queue for N times){
Contain a negative cycle.
}
}
Out_data; }
在一般情况，SPFA的效率很高，可以证明1SPFA的期望复杂度为O(KM)，K<2。但由于证明还不够严谨且适用性不广(存在针对性数据)，在此不再赘述。但将会在随后的测试中用实际数据来验证SPFA的高效性。
}
Halt;
1.2活学活用：SPFA的深度优先实现及其优化
1.2.1:基于Dfs的SPFA的基本原理
在上面的介绍的算法中，我们用一个循环队列来存储需要继续迭代的节点，实现时使用类似广度优先搜索的方式。那么我们是否可以使用搜索的另一利器：深度优先呢？
回忆之前的算法，由于采用广度优先的思想，每当我们扩展出一个新的节点，
1
证明见2006余远铭论文《最短路算法及其应用》
- 第5页共37页 -
2009Thesis SPFA的优化与应用 姜碧野
总是把它放到队列的末尾，其缺点是中断了迭代的连续性。而实际上如果采用深度优先的思想，我们可以直接从这个新节点继续往下扩展。于是算法的实现方式可以改成不断从新节点往下递归进行求解。
而对于负环的判断则显得更为简单，因为假如存在负环a1->a2->….ak->a1，
那么算法运行时，会从某个点a1开始Dfs，最后又回到了这个点。所以只需用一个辅助数组记录当前节点是否在递归栈中便可及时检测出负环。 伪代码如下：
Void SPFA(Node) {
Instack[Node]=true; For (Node,v) ∈E
If dis[Node]+edge(Node,v) dis[v]=dis[Node]+edge(Node,v); If not Instack[v] then SPFA(v); Else{ Contain an negative cycle. Halt; } } 两种算法的原理相同，相对Bellman-Ford的优化也是殊途同归的。其精髓都 Instack [Node] =false; } 在于只保存有用的状态。 那么，SPFA的这种实现效率如何呢？在随后的初步尝试中，笔者发现，在一 些拓扑关系比较强的时候，广度会有很大的优势。Dfs往往由于不断盲目地迭代而耗费了太多时间甚至远远超过时间的限制。 因此在下文中，笔者将结合深度优先搜索的特点，尝试对其进行优化。 - 第6页共37页 - 2009Thesis SPFA的优化与应用 姜碧野 1.2.2:基于Dfs的SPFA的相关优化 Dfs的实现方式虽然暂时无法取得好的效果，但我们并不应该就此放弃，Dfs 相对Bfs灵活的架构必能给予我们广阔的优化空间。 首先，一个很自然的想法便是改变搜索顺序，即把边按照一定的规则排序， 在这里当然是把边权按优劣排序，这样便可以得到一个不错的初始解。加入了这 个优化后，在某些数据上取得了不错的效果，但许多数据依然远远超过时间限制。 接着笔者联想到网络流使用贪心初始流进行优化的方法，因为当前解的优劣程度对之后的迭代有很大影响。而且Dfs的低效很大程度上是因为频繁地使用较次解去更新大片的元素。 由此我们可以考虑先在第一次Dfs时，对扩展节点采取一些限制以快速求得一个较优解，然后再进行第二次完整的Dfs。笔者经过多次尝试，在针对随机数据上得出一种不错的贪心初始解方法。 Function SPFA_Init (Node): Boolean { For (Node,v) ∈E If dis [Node] +edge (Node, v) Dis[v] =dis [Node] +edge (Node, v); SPFA_Init (v); Return true; } } Main { } 即对于每个节点只更新一个边后便退出。这一算法对于随机图能取得不错的效果，因为往往只更新一次能快速将当前值快速地传递。加入这个优化后效率有了很大提高，但与Bfs还是有不少差距。 - 第7页共37页 - Return false; For Node∈V While SPFA_Init(Node)do； For Node∈V SPFA (Node) 2009Thesis SPFA的优化与应用 姜碧野 于是笔者转而分析Bfs与Dfs的不同，经过比较可以发现Bfs的优势主要体现在某个点出队前可能再次被更新而得到更优的解进行下一次迭代。而Dfs往往会用一个次解进行层次很深的迭代(一个次解会导致O(N)级别的更新)。由此，可以联想到深度优先搜索的一个改进版本：迭代加深搜索，结合前面贪心初始解的原理，我们可以通过限制节点递归的深度并逐步放宽限制求解。 加入这个优化后，笔者欣喜地发现，在Bfs不擅长的网格形数据中，Dfs所用时间仅为Bfs的1/3，效率飞速提高，优势明显。而在一些其他随机数据中效果则有好有坏，总体还是比Bfs略逊一筹，但差距已不大。值得注意的是：对深度限制的不同，时间效率也有差异，笔者总结出了两种效果相对不错的限制方法： 1依次设置深度上限为1,2,4,8,16,32,64…..2^k….. maxlongint 2依次设置深度上限为20，30，40，50，60，80，100….maxlongint 鉴于Dfs在网格图上的高效，笔者即将其应用在Spoj的skivall一题中。该题的一个可行算法即为网格图上的费用流。使用Dfs后，效率得到了很大提升，仅用3s多就通过了全部数据。而且在USACO Jan09 Travel一题的数据中，DFS相比BFS有大幅提高，甚至优于dijikstra。(当然与数据的特性有关) 至此，对Dfs的优化也就告一段落了。但可以预见，Dfs可行的优化远远不 止如此，还有许多性质没有得到很好的利用。而且在上文的优化中，笔者并没有牺牲SPFA的简洁性(几乎不需要怎么修改原程序)，因此许多诸如加入优先队列(堆)等方法还有待研究。也希望上文的方法能激发读者的思路，继续探索新的优化方法,或是将这类优化思想应用在其他相关领域。 1.3 SPFA算法实际效果测试及比较 本节我们将用实际数据对SPFA进行测试 测试平台：CPU: Genuine Intel T2300 1.66 GHz 内存：512MB 测试器:伟栋清橙测试器1.0 测试说明: 1．测试项目为单源到其他全部顶点的最短路。运行时间包含读入 据时间。输出经过优化，可以忽略输出时间。 - 第8页共37页 -