图论:最短路-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 ;
}