这篇随笔讲解信息学奥林匹克竞赛中图论部分的求最短路算法SPFA的两种优化方式。学习这两种优化算法需要有SPFA朴素算法的学习经验。在本随笔中SPFA朴素算法的相关知识将不予赘述。

上课！

顾名思义，这种优化采用的方式是把较小元素提前。

就像dijkstra算法的堆优化一样。我们在求解最短路算法的时候是采取对图的遍历，每次求最小边的一个过程，为了寻找最小边，我们需要枚举每一条出边，如果我们一上来就找到这个边，那当然是非常爽的。一次找一次爽，一直找一直爽。所以我们采用了这种优化方式。

具体实现方式是把原来的队列变成双端队列，如果新入队的元素比队首元素还要小，就加入到队首，否则排到队尾。

模板如下：

void spfa()

{

memset(dist,0x3f,sizeof(dist));

memset(v,0,sizeof(v));

deque<int> q;

q.push_back(1);

v[1]=1;

dist[1]=0;

while(!q.empty())

{

int x=q.front();

q.pop_front();

v[x]=0;

for(int i=head[x];i;i=nxt[i])

{

int y=to[i];

if(dist[y]>dist[x]+val[i])

{

dist[y]>dist[x]+val[i];

if(v[y]==0)

{

if(dist[y]<=dist[q.pront()])

q.push_front(y);

else

q.push_back(y);

v[y]=1;

}

}

}

}

}

顾名思义，它的策略是把大的元素放到后面。

你会说，这不跟上面的一样么？

不不不，这个优化针对的是出队元素。它的实现过程是：对于每个出队元素，比较它的dist[]和队列中dist的平均值，如果它的dist[]更大，将它弹出放到队尾。以此类推，直至dist[x]小于其平均值。

模板：

void spfa()

{

memset(dis, 0x3f, sizeof(dis));

queue<int> q;

q.push(1);

v[1]=1;

dist[1]=0;

cnt=1;

while(!Q.empty())

{

int x=q.front();

while (dis[x]*cnt > sum)

{

q.pop();

q.push(x);

x=q.front();

}

q.pop();

cnt--;

sum -=dist[x];

v[x]=0;

for (int i=head[x]; i ; i=nxt[i])

{

int y=to[i];

if (dist[y]> dist[x]+ val[i])

{

dist[y]=dist[x]+ val[i];

if (v[y]==0)

{

q.push(y);

sum +=dist[y];

cnt++;

}

}

}

}

}

听名字就很高级。

是的，的确很高级，不仅高级，而且快。

我就直接上模板了。

void spfa()

{

memset(dist, 0x3f, sizeof(dist));

memset(v,0,sizeof(v));

deque<int> q;

q.push_back(1);

v[1]=1;

dist[1]=0;

cnt=1;

while (!q.empty())

{

int x=q.front();

while (cnt*dist[x]> sum)

{

q.pop_back();

q.push_back(x);

x=q.front();

}

q.pop_front();

cnt--;

sum -=dist[x];

v[x]=0;

for (int i=head[x]; i ; i=nxt[i])

{

int y=to[i];

if (dist[y]> dist[x]+ val[i])

{

dist[y]=dist[x]+ val[i];

if (!v[y])

{

if (dist[y]<=dist[q.front()])

q.push_front(y);

else

q.push_back(y);

v[y]=1;

sum +=dist[y];

cnt++;

}

}

}

}

}