420
spfa優化 SLF LLL
2013.10.23 更新
之前寫的時候不知道在想什麼，整理模板時才發現寫挫了，現在重發一個
SPFA 是按照 FIFO 的原則更新距離的, 沒有考慮到距離標號的作用. 實現中 SPFA 有兩個非常著名的優化: SLF 和 LLL.
SLF: Small Label First 策略.
實現方法是, 設隊首元素為 
,
隊列中要加入節點 
,
在 
時加到隊首而不是隊尾, 否則和普通的 SPFA 一樣加到隊尾. 這可以用個優先級隊列維護
LLL: Large Label Last 策略.
實現方法是, 設隊列 
中的隊首元素為 ,
距離標號的平均值為 
,
每次出隊時, 若 
,
把
移到隊列末尾, 如此反複, 直到找到一個
使 
,
將其出隊.
/**
複雜度分析：
普通SPFA km kmax=n 不適合稠密圖 一般為2
優先級隊列 加入節點複雜度logn 節點數太多時適得其反，對於特殊數據速度略小於普通spfa
對於隨機圖效果很好
手動模擬SLF，LLL 複雜度低於優先級隊列，最壞情況與普通SPFA持平
*/
#define Maxn 100010//最大點數
#define Maxm 400010//最大邊數，無向圖要建雙向邊
int w[Maxm],u[Maxm],next[Maxm],cnt;
int first[Maxn],havein[Maxn];//havin為入隊次數
long long d[Maxn];//距離
int n;
bool in[Maxn];//隊中標誌
inline void add(int vn,int un,int wn){//鄰接表存儲
u[cnt]=un;w[cnt]=wn;next[cnt]=first[vn];first[vn]=cnt++;
}
struct node{
int v,dd;
node(int &a):v(a),dd(d[a]){};
bool operator< (const node& a)const{
return dd>a.dd;
}
};
priority_queue<node> q; //利用優先級隊列SLF和LLL
bool spfa(int s){
int i,now,ne,t;
memset(in,0,sizeof(in));
memset(havein,0,sizeof(havein));
for(i=0;i<n;i++)d[i]=INF; //memset(d,0x3f,sizeof(d));
d[s]=0;in[s]=1;q.push(s);
while(!q.empty()){
now=q.top().v;q.pop();
if(!in[now])continue;
in[now]=0;
for(i=first[now];~i;i=next[i]){
ne=u[i];
if(d[ne]<=(t=d[now]+w[i]))continue;
d[ne]=t; in[ne]=1; q.push(ne);
if(++havein[ne]>n)return 0;//判斷有無負環
}
}
return 1;//返回1為正常，0為有負環
}
#define M 200000 //手動模擬
int q[M];
bool spfa(int s){
int i,now,ne,t;
memset(in,0,sizeof(in));
memset(havein,0,sizeof(havein));
memset(d,0x3f,sizeof(d));
int l,r,len;l=r=len=0;
long long sum=0;
d[s]=0;in[s]=havein[s]=1;
q[r++]=s;len++;
while(l!=r){
now=q[l++];
if(l==M)l=0;
if(d[now]*len>sum){//LLL
q[r++]=now;
if(r==M)r=0;
continue;
}
len--; sum-=d[now]; in[now]=0;
for(i=first[now];~i;i=Next[i]){
ne=u[i];
if(d[ne]<=(t=d[now]+w[i]))continue;
d[ne]=t;
if(in[ne])continue;
in[ne]=1;
if(t<=d[q[l]]){ //SLF
if(--l<0)l=M-1;
q[l]=ne;
}
else{
q[r++]=ne;
if(r==M)r=0;
}
len++; sum+=t;
if(++havein[ne]>n)return 0;
}
}
return 1;//返回1為正常，0為有負環
}
void init()//邊初始化
{
cnt=0;
memset(first,-1,sizeof(first));
}
最後更新：2017-04-02 00:06:49