最短路之SPFA模板
来源：程序员人生 发布时间：2015-03-28 08:24:11 阅读次数：3398次
1：邻接矩阵版本SPFA//如果要判断负环的话加1个记录入队的数组就行，当入队次数大于n的时候出现负环
int d[MAXN],vis[MAXN],w[MAXN][MAXN];
int n;
void SPFA(int s)
{
fill(d,d+n,INF);
d[s]=0;
queue<int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=0; v<n; v++)
{
if(d[v]>d[u]+w[u][v])
{
d[v]=d[u]+w[u][v];
q.push(v);
}
}
}
}
2：伪邻接表版SPFA
const int inf = 0x3f3f3f3f;
int v[M],w[M],next[M],head[N],d[N],e;//head初始化为⑴，摹拟邻接表
void addedge(int a,int b,int x)//主要如果是无向图的话,每条边要履行两次这个，a,b反过来就行
{
v[e]=b;
w[e]=x;
next[e]=head[a];
head[a]=e++;
}
void SPFA(int s)
{
queue<int> q;
d[s]=0;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i=head[u]; i!=⑴; i=next[i])
{
if(d[v[i]]>d[u]+w[i])
{
d[v[i]]=d[u]+w[i];
q.push(v[i]);
}
}
}
}
for(int i=0; i<m; i++)//输入1条带权值的无向边
{
cin>>a>>b>>x;
addedge(a,b,x);
addedge(b,a,x);
}
3：邻接表版
struct Edge
{
int to,w,next;
}E[maxn];
void init()
{
memset(head,⑴,sizeof(head));
fill(d,d+n,INF);
size = 0;
}
void addedge(int u,int v,int x)
{
E[size].to = v;
E[size].w = x;
E[size].next = head[u];
head[u] = size++;
}
void SPFA(int s)
{
queue<int> q;
d[s]=0;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i=head[u]; i!=⑴; i=E[i].next)
{
if(d[E[i].to] > d[u] + E[i].w)
{
d[E[i].to] = d[u]+E[i].w;
q.push(E[i].to);
}
}
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
