《05SPFA算法》由会员分享，可在线阅读，更多相关《05SPFA算法（21页珍藏版）》请在金锄头文库上搜索。
1、SPFA算法,SPFA 全称 Shortest Path Faster Algorithm基本应用为快速求解单源最短路,Spfa算法可以说是beelman算法的改进版.spfa是利用队列来动态更新最小值. 它的工作方法是这样:每次取出队头的顶点K,对于所有与他相邻的点I,我们进行如下操作:判断从点K到点I的值是否u，设边的长度为len，判断Distv+len是否小于Distu，若小于则改进Distu，将Fau记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入
2、队次数超过n，则有负权环。,SPFA算法实现,SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。,伪代码描述：,wi,j表示i,j的权si,j表示i到j的最短路repeat for 所有边i,j if so,i+wi,jso,j then 更新so,juntil 没有改变,伪代码描述：,这种算法适用于所有类型的图（SSSP），如果要求任两个点的最短路径(APSP)，则要重复n次 有几个优化：
3、 1.可以先判断是否有负权自环，有则直接输出-1 2.在枚举的过程中，当这个顶点的最短路(di)0时，有负权回路，输出-1.,void spfa(int s) int q101,v101,h=0,t=1,x,i; /q为队列,v为Boolean数组,表示结点是否在队列中,h为头指针,t为尾指针 memset(q,0,sizeof(q); memset(v,0,sizeof(v); for(i=0;i101;i+) disti = INT_MAX; /这里应该用for循环初始化，memset函数只能将值初始化为0或者-1。 dists=0; qt=s;vs=1; while(h!=t) /本来是
4、ht,但这不是循环队列么,不能这么干的. h=(h+1)%(n+1);/这里不能%n否则队满和队空状态一样 x=qh; vx=0; for(i=1;idistx) /这里本来为distidistx+axi,但这样会越界的,因为后两者加起来太大 disti=distx+axi; if(!vi) t=(t+1)%(n+1)/*同上*/;qt=i;vi=1; ,Relax(u,v)If （F(v)F(u)+W_Cost(u,v)）F(v)=F(u)+W_Cost (u,v);,SPFA的核心正是松弛操作：,但松弛操作直接得出的Bellman-Ford算法效率低下 For Time=1 to N Fo
5、r (u,v)ERelax(u,v),上图数据中，总运算量高达N2而边(S, A1)虽然被调用N次。但实际有用的只有一次,SPFA则使用队列进行了优化！,思想： 只保存被更新但未扩展的节点。 减少了大量无用的计算，效率大大提高！,在上图的例子中，每个节点只进队一次，只需N次运算。相比Bellman-Ford优势明显。,我们再从另一个角度来分析DIJ和spfa,Dij的思想可以从另一个角度来阐述：一个点的最短路必定从另一个点的最短路推导出，而另一个点的最短路必定disNode+w(Node,v) ） disv=disNode+w(Node,v); SPFA_Dfs (v); ,核心思想:每次从刚
6、刚被更新的节点开始递归进行下一次迭代！,后进先出！,判断存在负环的条件： 重新经过某个在当前搜索栈中的节点,相比队列，深度优先有着先天优势： 在环上走一圈，回到已遍历过的点即有负环。绝大多数情况下时间为O(M)级别。,实战:WordRings(ACM-ICPC Centrual European2005) 676个点，100000条边，查找负环。DFS只需219ms！,一个简洁的数据结构和算法在一定程度上解决了大问题。,优美的SPFA！,最坏情况下需要KM次运算,优化：随机调整边的顺序 则期望k+mLogk,优化无止境！,还有不足吗？,最短路问题其实只是SPFA迭代思想在图论中的一个特例，在其他各类动态规划，迭代法解方程，不等式等问题中往往也能发挥奇效！,
