先舉出個例題：洛谷P3371 【模板】單源最短路徑

一眼掃去：最短路徑。

spfa不接受反駁。。。

附上代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #define MAXN 10010 #define MAX 999999999 using namespace std; int n,m,s,c=1; int head[MAXN],path[MAXN]; bool vis[MAXN]; struct node{int next,to,w; }a[MAXN*100]; inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } inline int relax(int u,int v,int w){if(path[v]>path[u]+w){path[v]=path[u]+w;return 1;}return 0; } inline void add(int u,int v,int w){a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++; } void spfa(){int u,v;queue<int> q;for(int i=1;i<=n;i++){path[i]=MAX;vis[i]=false;}path[s]=0;vis[s]=true;q.push(s);while(!q.empty()){u=q.front();q.pop();vis[u]=false;for(int i=head[u];i;i=a[i].next){v=a[i].to;if(relax(u,v,a[i].w)&&!vis[v]){vis[v]=true;q.push(v);}}}for(int i=1;i<=n;i++)printf("%d ",path[i]==MAX?2147483647:path[i]); } int main(){int u,v,w;n=read();m=read();s=read();for(int i=1;i<=m;i++){u=read();v=read();w=read();add(u,v,w);}spfa();return 0; }

然而遇到某些坑爹的題，比如USACO上的某些題，硬生生卡spfa啊！怎么辦？

沒事，我們有優化——SLF與LLL！

?

---

SLF優化：

SLF優化，即 Small Label First ?策略，使用 雙端隊列 進行優化。

一般可以優化15%~20%，在競賽中比較常用。

設從 u 擴展出了 v ，隊列中隊首元素為 k ，若 dis[ v ] < dis[ k ] ，則將 v 插入隊首，否則插入隊尾。

注：隊列為空時直接插入隊尾。

附代碼：

?

#include<iostream> #include<algorithm> #include<cstdio> #include<deque> #define MAXN 10010 #define MAXM 500010 #define MAX 2147483647 using namespace std; int n,m,s,t,c=1; int head[MAXN],path[MAXN]; bool vis[MAXN]; struct node{int next,to,w; }a[MAXM<<1]; inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } inline int relax(int u,int v,int w){if(path[v]>path[u]+w){path[v]=path[u]+w;return 1;}return 0; } inline void add(int u,int v,int w){a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++; } void spfa(){int u,v;deque<int> q;for(int i=1;i<=n;i++){path[i]=MAX;vis[i]=false;}path[s]=0;vis[s]=true;q.push_back(s);while(!q.empty()){u=q.front();q.pop_front();vis[u]=false;for(int i=head[u];i;i=a[i].next){v=a[i].to;if(relax(u,v,a[i].w)&&!vis[v]){vis[v]=true;if(!q.empty()&&path[v]<path[q.front()])q.push_front(v);else q.push_back(v);}}}for(int i=1;i<=n;i++)printf("%d ",path[i]);printf("\n"); } int main(){int u,v,w;n=read();m=read();s=read();for(int i=1;i<=m;i++){u=read();v=read();w=read();add(u,v,w);}spfa();return 0; }

?

---

LLL優化：

LLL優化，即 Large Label Last ?策略，使用 雙端隊列 進行優化。

一般用SLF+LLL可以優化50%左右，但是在競賽中并不常用LLL優化。

設隊首元素為 k ，每次松弛時進行判斷，隊列中所有 dis 值的平均值為 x 。

若 dist[ k ] > x ，則將 k 插入到隊尾，查找下一元素，直到找到某一個 k 使得 dis[ k ] <= x ，則將 k 出隊進行松弛操作。

附代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<list> #define MAXN 10010 #define MAXM 500010 #define MAX 2147483647 using namespace std; int n,m,s,t,c=1; int head[MAXN],path[MAXN]; bool vis[MAXN]; struct node{int next,to,w; }a[MAXM<<1]; inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } inline int relax(int u,int v,int w){if(path[v]>path[u]+w){path[v]=path[u]+w;return 1;}return 0; } inline void add(int u,int v,int w){a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++; } void spfa(){int u,v,num=0;long long x=0;list<int> q;for(int i=1;i<=n;i++){path[i]=MAX;vis[i]=false;}path[s]=0;vis[s]=true;q.push_back(s);num++;while(!q.empty()){u=q.front();q.pop_front();num--;x-=path[u];while(num&&path[u]>x/num){q.push_back(u);u=q.front();q.pop_front();}vis[u]=false;for(int i=head[u];i;i=a[i].next){v=a[i].to;if(relax(u,v,a[i].w)&&!vis[v]){vis[v]=true;if(!q.empty()&&path[v]<path[q.front()])q.push_front(v);else q.push_back(v);num++;x+=path[v];}}}for(int i=1;i<=n;i++)printf("%d ",path[i]);printf("\n"); } int main(){int u,v,w;n=read();m=read();s=read();for(int i=1;i<=m;i++){u=read();v=read();w=read();add(u,v,w);}spfa();return 0; }

---

后記：

附上洛谷上的三次提交：

樸素spfa：Accepted??100

?336ms /??7.92MB?
代碼：1.19KB C++

spfa+SLF：?Accepted??100

316ms /??7.89MB?
代碼：1.33KB C++

?

spfa+SLF+LLL：?Accepted??100

?316ms /??8.08MB?
代碼：1.45KB C++

顯然，SLF這個優化已經足夠了。

再說，就算卡spfa+優化，不就5~10分嘛。。。

$Update 2018.7.29:$：

$NOI2018Day1T1$竟然真的卡了$SPFA$！！！

并且卡了$40$分！！！

出題人你說你卡個$10$分、$20$分也就算了，居然卡了$40$分！！！

大毒瘤。。。

所以對于正權圖還是乖乖寫堆優化$Dijkstra$吧。。。

附上講解：

Dijkstra的堆優化

轉載于:https://www.cnblogs.com/Yangrui-Blog/p/8997721.html

總結

以上是生活随笔為你收集整理的SPFA的两个优化：SLF与LLL的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。