SPFA算法.

SPFA算法广东中山纪念中学姜碧野常见问题：1、在负权图上判断是否存在负环2、解决有环的动态规划转移方程这些问题该如何解决？内容概要第一部分简要介绍SPFA的基本实现第二部分提出SPFA一种新的实现方式第三部分介绍如何灵活使用SPFA解题在本文中将看到：SPFA全称ShortestPathFasterAlgorithm基本应用为快速求解单源最短路灵活多变相比其他同类算法有什么优点呢？让我们来一起领略！简洁优美适用面广Relax(u,v){IfF(v)F(u)+W_Cost(u,v)thenF(v)=F(u)+W_Cost(u,v);}SPFA的核心正是松弛操作：.......A1TAnS但松弛操作直接得出的Bellman-Ford算法效率低下ForTime=1toNFor(u,v)∈ERelax(u,v)上图数据中，总运算量高达N^2而边(S,A1)虽然被调用N次。但实际有用的只有一次SPFA则使用队列进行了优化！思想：只保存被更新但未扩展的节点。减少了大量无用的计算，效率大大提高！A1A2…….A4An-1A3AnHeadTail当前待扩展元素在上图的例子中，每个节点只进队一次，只需N次运算。相比Bellman-Ford优势明显。.......A1TAnS但有负环时依然退化为O(NM)在1000000个点，2000000条边的随机数据中SPFA甚至比使用堆优化的Dijkstra还要快。A1TAnS长期以来基于队列的SPFA并未取得突破传统的队列实现:缺点：NewNode需要之前的元素全部出队后才能扩展中断了迭代的连续性猜想：能否把NewNode放在Head后面进行下一次扩展？A1A2…….A4An-1A3AnHeadTailNewNode猜想程序图论中的基本算法：深度优先搜索基本数据结构：栈SPFA_Dfs(Node){For(Node,v)∈EIfdis[v]dis[Node]+w(Node,v)thendis[v]=dis[Node]+w(Node,v);SPFA_Dfs(v);}}核心思想:每次从刚刚被更新的节点开始递归进行下一次迭代！后进先出！判断存在负环的条件：重新经过某个在当前搜索栈中的节点A1TAnS相比队列，深度优先有着先天优势：在环上走一圈，回到已遍历过的点即有负环。绝大多数情况下时间为O(M)级别。实战:WordRings(ACM-ICPCCentrualEuropean2005)676个点，100000条边，查找负环。DFS只需219ms！一个简洁的数据结构和算法在一定程度上解决了大问题。SA1A2AkAk-1…......B1…….B2BmT+∞最坏情况下需要KM次运算优化：随机调整边的顺序则期望k+mLogk还有不足吗？让我们结合一道题目来进行探讨最短路问题其实只是SPFA迭代思想在图论中的一个特例，在其他各类动态规划，迭代法解方程，不等式等问题中往往也能发挥奇效！苹果争夺战两个人A,B在一个5*6的矩阵里抢夺苹果。矩阵包含空地，4棵苹果树和障碍物，每个苹果树上有3个苹果。A先行动，然后两人轮流操作，每一回合每人可以向四周移动一格或停留在一棵苹果树下，如果苹果树非空可以摘下一个苹果。两人不能移动到矩阵外，障碍物上或是对方的位置，且两人绝顶聪明。问A最多可以抢到多少个苹果。此时B不能再向左移动而A可以逐步摘下3棵树的所有苹果开始时A无法移动之后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)G[X,Y,K]=Min(F[X’,Y’,K’])但是….单纯的状态转移会出现环，怎么办呢？解决存在环的动态规划，常规思路:一：利用标号法通过已经得出最优解的状态递推出其他状态。值最大的？但G[]可能被其他较小的F[]更新，并不是最优解。值最小的？F[]同样可能被其他更大的G[]更新，因此标号法并不适用如何找出最优解？思路二：参考负权图上求最短路的思想通过局部的较优值一步步迭代得到最优解假设当前解为：G[]=F[]=5354之后G[]得出最优解4两种常规解法都失败了，我们需要从新的角度来思考猜想：能否越过状态间纷繁复杂的转移关系直接考虑最终状态呢？回归原方程：F[X,Y,K]=Max(G[X’,Y’,K’]+Apple)G[X,Y,K]=Min(F[X’,Y’,K’])既是转移方程，也是终状态联想：SPFA在图论求最短路中的本质：三角不等式：最短路的终状态，对于所有边(u,v)∈E有distance(s,v)=distance(s,u)+w(u,v)。当某边三角不等式不成立时，用松弛操作调整之。在本题中适用吗？同样：F[X,Y,K]=Max(G[X’,Y’,K’]+Apple)是问题的终状态G[X,Y,K]=Min(F[X’,Y’,K’])一旦方程整体不成立便重赋值！算法：先对边界状态赋初值为0。使用SPFA不断考察每条转移方程是否成立，不成立则更新。将松弛操作推广！假设当前解为：G[]=F[]=5345之后G[]得出最优解2G’[]=4F[]=MAX(G[],G’[])2特点:赋值时考虑的是一个整体，即需要在所有与当前节点关联的状态中取最值，保证了合法性。G[]被更新时F[]还要重新考虑G’[]。性质1：该算法结束时求得的解为正确解。证明：该结论显然，算法结束意味各个方程均成立性质2：该算法一定会结束。证明：把状态按照其最终值的大小分层，则可以发现当前K层确定时，对于第K+1层有：1.G[]可以从前K+1层取得最小值。2.F[]的最大值只能从前K+1层取，否则其最终值不可能为K+1。因此状态会逐层确定并最终停止。算法正确吗？让我们继续分析。回顾思考过程，我们似乎感到：最终算法完完全全建立在原方程之上，没有转弯，没有变形，只需“简单机械”地赋值。而与之类似的传统迭代法却并不可行。更新时需遍历所有相关节点(本题算法)更新时只需考虑点对间关系(最短路迭代算法)每个节点只扩展一次(标号法)利用标号法则使用贪心思想再优化优化：利用最短路问题中当前解只会成为次优解，而不会成为非法解的性质。不！让我们对比几种算法。三者的本质都是统一的，但随着算法的优化适用面逐步缩窄优化算法是好的，但如果没有对算法有着深刻的认识，忽略了算法的适用条件，思维的定势很容易使我们得出错误算法。总结在查找负环中，抛开了传统的实现方式，我们得出一种崭新的架构使效率大大提高在动态规划中，摆脱了思维定势的影响，我们才得出正确的解法。SPFA并不是一个死板的经典算法，我们只有灵活运用才能发挥其应有的奇效。在对Bellman-Ford算法的合理优化中，诞生了高效的SPFA算法。灵活