图论：最短路-SPFA

时间：2023-02-15 13:37:56

该算法由Bellman-Ford算法演变过来，首先介绍一下Bellman-Ford算法

最短路最多经过n-1个点，可以用n-1轮松弛操作来得到

for(int i=;i<n;i++)

    d[i]=INF;

d[]=;

for(int k=;k<n-;k++)

for(int i=;i<m;i++)  //检查每条边

{

    int x=u[i];

    int y=v[i];

    if(d[x]<INF)

        d[y]=min(d[y],d[x]+w[i]);

}

当然这个算法我没有实际应用过，而是一直在用它的优化算法，利用队列代替前面的循环检查

SPFA最坏时间复杂度仍然为O（nm），但是有人分析其时间复杂度为O（km）,k为每个点入队次数，正确性未知

SPFA和Bellman-Ford都可以检测负环但是只有后者可以输出负环

下面给出邻接表实现的SPFA算法，可以求出单源最短路。

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int maxn=;

 const int maxm=;

 const int INF=0x7fffffff;

 //

 int n,m,s;

 //

 int g[maxn];

 struct point

 {

     int t,w,next;

 }e[maxm];

 int d[maxn];

 //

 int tot=;

 void addedge(int a,int b,int c)

 {

     tot++;

     e[tot].t=b;

     e[tot].w=c;

     e[tot].next=g[a];

     g[a]=tot;

 }

 //

 int q[maxn];

 bool v[maxn];

 void spfa(int x0)

 {

     for(int i=;i<=n;i++)

     d[i]=(i==x0?:INF);

     int h=,t=;

     q[t]=x0;

     while(h!=t)

     {

         h=h%maxn+;

         int x=q[h];

         v[x]=false;

         for(int tmp=g[x];tmp;tmp=e[tmp].next)

         {

             if(d[e[tmp].t]>d[x]+e[tmp].w)

             {

                 d[e[tmp].t]=d[x]+e[tmp].w;

                 if(!v[e[tmp].t])

                 {

                     v[e[tmp].t]=true;

                     t=t%maxn+;

                     q[t]=e[tmp].t;

                 }

             }

         }

     }

 }

 int main()

 {

     cin>>n>>m>>s;

     for(int i=;i<=m;i++)

     {

         int x,y,z;

         cin>>x>>y>>z;

         addedge(x,y,z);

     }

     spfa(s);

     for(int i=;i<=n;i++)

         cout<<d[i]<<" ";

     return ;

 }

相关文章