首页 > > 程序设计 > C/C++ >

spfa

2018-06-17 23:47:50来源：未知阅读 ()

这篇文章来介绍一下spfa（Shortest Path Faster Algorithm）这种算法

这是一种单源最短路的一种十分高效的的算法。

我们需要用邻接表来存储一下图，以及用队列进行优化。

我们以1为起点，以n为终点来讲一下（一共n个点）

用L数组记录当前点的最短路

先把每一条边的最短路赋成最大值（赋多少自己决定，反正得大一点）

我们先把1入队

因为我们用的是队列进行优化，所以每次取出队首元素s，对s所连接每一个点x进行如下操作

如果L[s]+s--x的长度比L[x]要短，那么便更新L[x]，再判断x是否已经入队，若没有入队，则将x放入队中（这里需要注意一点，若x这个点入队的次数已经超过了n次，那么说明有负权环（spfa处理不了带有负权环的图），当然要是题目告诉了不存在负权环就不需要了）。

void add(int aa,int bb,int cc)
{
 b[++cnt].v=bb;//当前点所连的边
 b[cnt].next=hh[aa];//上一条以当前点为起点的边的序号
 b[cnt].z=cc;//路的长度
 hh[aa]=cnt;//邻接表中最近的一条起点为当前点的边的序号    
}
int main()
{
 scanf("%d %d",&n,&m);
 for(i=1;i<=m;i++)
 {
  scanf("%d %d %d",&x,&y,&w);//起点，终点，长度
  add(x,y,w);add(y,x,w);//邻接表用来存边，当然，如果是单向边的话，
                                                                       // 就只做其中一个
 }
 
 memset(l,0x3f,sizeof(l));//将每一条路的最短距离赋为最大值
 l[1]=0;//起始点为点1，所以到点1的最短距离是0
 x=1;//现在的x为起点，当然也可以是其它点
 while(1)
 {
  if(h>t)break;
  j=hh[x];
  while(1)
  {
   e=b[j].v;
   if(l[x]+b[j].z<l[e]){
       l[e]=l[x]+b[j].z;
       p[e]=x;
       if(dd[e]==false)dd[e]=true,d[++t]=e;//dd数组记录的是当前点是否在队列中，如果不在就将其入队；
//dd判断的是该点是否在队中（所以可以用bool类型）
   }
   if(b[j].next==0)break;//如果邻接表中在此之前没有以当前点为起点的边那么就打断循环
   j=b[j].next;
  }
  dd[x]=false;//对当前点所连的所有点已经进行了松弛操作，那么这个点就会出队，那么它的状态便是不在队中了
//如果题目中可能存在负环，那么需要开一个数组记录这个点的入队次数，超过n次则证明存在负环
  x=d[++h];//将x换为队首元素
  
 }
//执行完以上代码后，l[i]则代表的是起点到当前点的最短距离