先举出个例题：洛谷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$吧。。。
附上讲解：