文档介绍：SPFA 算法 2011 寒假集训 SPFA 全称 Shortest Path Faster Algorithm 基本应用为快速求解单源最短路? Spfa 算法可以说是 beelman 是利用队列来动态更新最小值. ?它的工作方法是这样:每次取出队头的顶点 K,对于所有与他相邻的点 I,我们进行如下操作:判断从点 K到点 I的值是否<当前的最小距离,如果是,则更新最小值,并且看看 I是否在队列里,如果不在,则将点 , 算法还是比较好理解的,spfa 算法是属于那种标号修正法类的. SPFA 算法实现?设 Dist 代表 S到I点的当前最短距离, Fa 代表 S到I的当前最短路径中 I点之前的一个点的编号。开始时 Dist 全部为+∞,只有 Dist[S]=0 , Fa 全部为 0。?维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个点 S。用一个布尔数组记录每个点是否处在队列中。 SPFA 算法实现?每次迭代,取出队头的点 v,依次枚举从 v 出发的边 v->u ,设边的长度为 len ,判断 Dist[v]+len 是否小于 Dist[u] ,若小于则改进 Dist[u] ,将 Fa[u] 记为 v,并且由于 S到u的最短距离变小了,有可能 u可以改进其它的点,所以若 u不在队列中,就将它放入队尾。这样一直迭代下去直到队列变空,也就是 S 到所有的最短距离都确定下来,结束算法。若一个点入队次数超过 n,则有负权环。 SPFA 算法实现? SPFA 在形式上和宽度优先搜索非常类似, 不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列,但是 SPFA 中一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本身被改进,于是再次用来改进其它的点,这样反复迭代下去。伪代码描述: ? w[i,j] 表示 i,j的权? s[i,j] 表示 i到j的最短路? repeat ? for 所有边[i,j] ? if s[o,i]+w[i,j]<s[o,j] then 更新 s[o,j] ? until 没有改变伪代码描述: ?这种算法适用于所有类型的图( SSSP ), 如果要求任两个点的最短路径(APSP) ,则要重复 n次?有几个优化: ? 1. 可以先判断是否有负权自环,有则直接输出-1 ? 2. 在枚举的过程中,当这个顶点的最短路(d[i])<0 时,有负权回路,输出-1. void spfa(int s) { int q[101],v[101],h=0,t=1,x,i; //q 为队列,v为 Boolean 数组,表示结点是否在队列中,h为头指针,t为尾指针 memset(q,0,sizeof(q)); memset(v,0,sizeof(v)); for(i=0;i<101;i++) dist[i] = INT_MAX; // 这里应该用 for 循环初始化, memset 函数只能将值初始化为 0或者-1。 dist[s]=0; q[t]=s;v[s]=1; while(h!=t) { // 本来是 h<t, 但这不是循环队列么,不能这么干的... h=(h+1)%(n+1);// 这里不能%n 否则队满和队空状态一样 x=q[h]; v[x]=0; for(i=1;i<=n;i++) if(dist[i]-a[x][i]>dist[x]) { // 这里本来为 dist[i]>dist[x]+a[x][i], 但这样会越界的,因为后两者加起来太大 dist[i]=dist[x]+a[x][i]; if(!v[i]) { t=(t+1)%(n+1)/ *同上* /;q[t]=i;v[i]=1; } } } } Relax(u,v){ If ( F(v)>F(u)+W_Cost(u,v) ) F(v)=F(u)+W_Cost (u,v); } SPFA 的核心正是松弛操作: ....... A 1T An S 但松弛操作直接得出的 Bellman-Ford 算法效率低下 For Time=1 to N For (u,v) ∈E Relax(u,v) 上图数据中,总运算量高达 N^2 而边(S, A1) 虽然被调用 N次。但实际有用的只有一次