SPFA算法(Shortest Path Faster Algorithm),是经队列优化的单源最短路Bellman-Ford算法通常用于求含负权边的单源最短路径,以及判负权环。SPFA算法最坏情况下复杂度和朴素的Bellman-Ford算法相同,为O(VE),一般情况为O(kE),其中k为常数,由图的边权分布决定,所以复杂度不是很稳定,如若必须要避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。
从Bellman-Ford算法中我们得知,如果一个点上次没有被松弛过,那么下次就不会从这个点开始松弛,而每一遍松弛只是从源点出发树状地一层一层扩张,所以每一遍去试着松弛全部的边实在是太浪费时间,因此SPFA的思路是:将上一次松弛过的点放入队列,只松弛与队列中的点有关的边,就可以忽略掉那些不可被松弛的边,而且利用队列循环松弛,动态逼近路径的最优解,即最短路。
具体过程描述:dis数组全部初始化为INF,vis数组全部初始化为false,源点s,dis[s] = 0,将s放入队列,vis[s] = true,开始类似BFS的循环过程:队首出队,vis[队首] = false(这里跟BFS不同,因为当前队首的dis值可能不是最优解,有可能要再次入队),将其与其子点之间的边分别试着松弛,可松弛的话若子点vis为false,vis[子点] = true,子点入队。不断循环该过程,直至队空。
这就相当于从源点开始,树状地层层更新其子点的dis值,因图是错综复杂的,所以所以点都有可能会被多次更新,那么当他们的dis值为正确的最短路值时便不再被更新,也不被看做子点,基于此,当找不到子点时,算法就结束了,所有点的dis值均已被更新为正确的最短路值。
原始SPFA代码:
链式前向星:
void SPFA(int s)
{
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++)
dis[i] = INF;
vis[s] = 1;
dis[s] = 0;
queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int cur = Q.front();
Q.pop();
vis[cur] = 0;
for(int i = head[cur]; i != -1; i = edge[i].nxt)
{
int ID = edge[i].to;
if(dis[ID] > dis[cur]+edge[i].val)
{
dis[ID] = dis[cur] + edge[i].val;
if(!vis[ID])
{
vis[ID] = 1;
Q.push(ID);
}
}
}
}
}
邻接矩阵:
void SPFA(int s)
{
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++)
dis[i] = INF;
vis[s] = 1;
dis[s] = 0;
queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int cur = Q.front();
Q.pop();
vis[cur] = 0;
for(int i = 1; i <= n; i++)
{
if(dis[i] > dis[cur]+Map[cur][i])
{
dis[i] = dis[cur] + Map[cur][i];
if(!vis[i])
{
vis[i] = 1;
Q.push(i);
}
}
}
}
}
SPFA算法有两种优化方式:SLF和LLL
SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j) < dist(i)则将j插入队首,否则插入队尾。
LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。
两者都一般可提速15%~20%,SLF+LLL甚至最高可提速50%,可随情况优化使用。