最短路之SPFA模板
來源：程序員人生 發布時間：2015-03-28 08:24:11 閱讀次數：3572次
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);
}
}
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
