算法简介
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。也有人说SPFA本来就是Bellman-Ford算法，现在广为流传的Bellman-Ford算法实际上是山寨版。
算法流程
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单：
设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。
维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。
SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右
Dist[i]：头到i当前最小距离
Cost[i,j]:邻接矩阵，i点到j
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
procedure spfa; begin fillchar(q,sizeof(q),0); h:=0; t:=0;//队列 fillchar(v,sizeof(v),false);//v[i]判断i是否在队列中 for i:=1 to n do dist[i]:=maxint;//初始化最小值 inc(t); q[t]:=1; v[1]:=true; dist[1]:=0;//这里把1作为源点 while h<>t do//h队列头下标，t队列尾下标 begin h:=(h mod n)+1;x:=q[h]; v[x]:=false; for i:=1 to n do if (cost[x,i]>0)and(dist[x]+cost[x,i]<dist[i]) then begin dist[i]:=dist[x]+cost[x,i]; if not(v[i]) then begin t:=(t mod n)+1; q[t]:=i;v[i]:=true; end; end; end; end; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <stdio.h> #include <string.h> #include <stdlib.h> int tab[1001][1001];//临接表 int v[1001];// 是否进过队 int dis[1001];//当前最短路 int n; void spfa(int p){//x为源点 int i,x; int h,r; int q[1001];//SPFA队列,通常情况下每个元素只进一次 memset (v,0,sizeof(v)); memset (dis,0,sizeof(dis)); for (i=1;i<=n;i++)dis[i]=0x4000000; q[1]=p; h=0;r=1; dis[p]=0; while (h<r){ h++; x=q[h]; for (i=1;i<=n;i++) if (dis[h]+tab[x][i]<dis[i]){ dis[i]=dis[x]+tab[x][i]; if (v[i]==0){ q[++r]=i; v[i]=1; } } } v[x]=0;//出队列 } int main(){ int i,j,m; int f,t,l; scanf("%d%d",&n,&m); memset(tab,0,sizeof(tab)); for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (i!=j)tab[i][j]=0x40000001;//maxlongint for (i=1;i<=m;i++){ scanf("%d%d%d",&f,&t,&l); tab[f][t]=l; tab[t][f]=l; } spfa(1); for (i=1;i<=n;i++) printf("%3d:%3d\n",i,dis[i]); system("pause"); } |