1. SLF优化
在我们学SPFA的时候，要把每一个入队的点插入到队尾，可是有些时候这个点作为队尾没有作为队头效率高，因为这个点有时放在队首就能直接用，那么什么样的点作为队首更好呢？当然是dis值越小越可能刷新其它\(dis\)值，所以对比当前元素与对首元素的\(dis\)值，如果当前元素的\(dis\)值更小，那么把当前元素插入到队首，否则插入到队尾。此时\(queue\)应该改为\(deque\)双端队列。
code
void SPFA()
{
memset(dis,inf,sizeof(dis));
deque<int>q;
q.push_back(1);dis[1]=0;vis[1]=1;
while(q.size())
{
x=q.front();q.pop_front();vis[x]=0;
for(int i=head[x];i;i=map[i].next)
{
s=map[i].to;
if(dis[s]>dis[x]+map[i].value)
{
dis[s]=dis[x]+map[i].value;
if(vis[s]==0)
{
if(dis[s]<dis[q.front()]) q.push_front(s);
else q.push_back(s);//新加
vis[s]=1;
}
}
}
}
}
2. LLL优化
如果懂了上一个SLF优化，那么这个LLL优化就很好理解了，SLF表示小的优先，LLL表示大的最后，那么什么样的的dis值是大的呢？难道还和队首元素比较吗？当然不是，是于队列的平均数来比较，如果大于这个平均数就放到最后。
code
void SPFA()
{
memset(dis,inf,sizeof(dis));
queue<int>q;
q.push(1);dis[1]=0;vis[1]=1;
while(q.size())
{
p=q.front();q.pop();
if(dis[p]*cnt_2>sum)
{
q.push(p);
continue;
}
sum-=dis[p];cnt_2--;//新加
vis[p]=0;
for(int i=head[p];i;i=map[i].next)
{
s=map[i].to;
if(dis[s]>dis[p]+map[i].value)
{
dis[s]=dis[p]+map[i].value;
if(vis[s]==0)
{
vis[s]==1;
q.push(s);
cnt_2++;
sum+=dis[s];//新加
}
}
}
}
}
2. SLF+LLL优化
code
void SPFA()
{
memset(dis,inf,sizeof(dis));
deque<int>q;
q.push_back(1);dis[1]=0;vis[1]=1;
while(q.size())
{
p=q.front();q.pop_front();
if(dis[p]*cnt_2>sum)
{
q.push_back(p);
continue;
}
sum-=dis[p];cnt_2--;
vis[p]=0;;
for(int i=head[p];i;i=map[i].next)
{
s=map[i].to;
if(dis[s]>dis[p]+map[i].value)
{
dis[s]=dis[p]+map[i].value;
if(vis[s]==0)
{
vis[s]==1;
if(dis[s]<dis[q.front()]) q.push_front(s);
else q.push_back(s);
cnt_2++;
sum+=dis[s];
}
}
}
}
}