SPFA Shortest Path Faster Algorithm 最短路径最快算法
算法思想
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。
最简单的模板
#define pii pair<int,int>
vector<pii> a[maxn]; //邻接表,存图
int dis[maxn]; //距离
void spfa(int s) //s源点
{
mem(dis,inf); dis[s] = 0;
queue<int> q;q.push(s);
while (!q.empty())
{
s = q.front();q.pop();
for(auto i : a[s])
{
if(dis[i.first] > dis[s]+i.second)
{
dis[i.first] = dis[s]+i.second;
q.push(i.first);
}
}
}
}
判断是否存在负环
int dis[maxn];
bool vis[maxn];
int out[maxn]; //出队次数
bool spfa(int s)
{
mem(dis,inf);dis[s] = 0;
queue<int> q;q.push(s);
while(!q.empty())
{
s = q.front();q.pop();vis[s] = 0;
out[s]++;if(out[s] >= n) return false; //存在负环
for(auto i : a[s])
{
if(dis[i.first] > dis[s]+i.second)
{
dis[i.first] = dis[s]+i.second;
if(!vis[i.first])
{
vis[i.first] = 1;
q.push(i.first);
}
}
}
}
return true; //不存在负环
}
SLF优化
SLF优化,即 Small Label First 策略,使用 双端队列 进行优化。也可以手写双端队列
一般可以优化15%~20%,在竞赛中比较常用。
设从 u 扩展出了 v ,队列中队首元素为 k ,若 dis[ v ] < dis[ k ] ,则将 v 插入队首,否则插入队尾。
注:队列为空时直接插入队尾。
#define pii pair<int,int>
vector<pii> a[maxn]; //邻接表,存图
int dis[maxn]; //距离
bool vis[maxn]; //标记,表示该点当前是否在队列中,在的话就不用进队了
void spfa_slf(int s)
{
mem(dis,inf); dis[s] = 0;
deque <int> q; //正常队列新元素插入队尾,双端队列可以选择
q.push_back(s);
while(!q.empty())
{
s = q.front(); //队首
q.pop_front(); //队首pop
vis[s] = 0;
for(auto i : a[s])
{
if(!vis[i.first] && dis[i.first] > dis[s]+i.second)
{
vis[i.first] = 1;
dis[i.first] = dis[s]+i.second;
if(!q.empty() && dis[q.front()] > dis[i.first]) q.push_front(i.first); //插入队首
else q.push_back(i.first); //否则插入队尾
}
}
}
}
LLL优化
LLL优化,即 Large Label Last 策略,使用 双端队列 进行优化。
一般用SLF+LLL可以优化50%左右,但是在竞赛中并不常用LLL优化。
设队首元素为 k ,每次松弛时进行判断,队列中所有 dis 值的平均值为 x 。
若 dist[ k ] > x ,则将 k 插入到队尾,查找下一元素,直到找到某一个 k 使得 dis[ k ] <= x ,则将 k 出队进行松弛操作。
void spfa_lll(int s)
{
for(int i = 1;i <= n; i++) dis[i] = inf;
dis[s] = 0;
deque<int> q;
q.push_back(s);
ll x = 0; int num = 1; //x是队列元素的和,num是队列元素的个数
while(!q.empty())
{
s = q.front();
q.pop_front();
num--; x -= dis[s];
while (num && dis[s] > x/num) //和slf的唯一区别
{
q.push_back(s); //就把s放到队尾
s = q.front(); //另取s
q.pop_front();
}
vis[s] = 0;
for(auto i : a[s])
{
if(!vis[i.first] && dis[i.first] > dis[s]+i.second)
{
dis[i.first] = dis[s]+i.second;
vis[i.first] = 1;
if(!q.empty() && dis[i.first] > dis[q.front()]) q.push_front(i.first);
else q.push_back(i.first);
num++,x += dis[i.first];
}
}
}
}
swap优化
每当队列改变时,如果队首距离大于队尾,则交换首尾。
void spfa(int s) //swap
{
for(int i = 1;i <= n; i++) dis[i] = 1e18;
dis[s] = 0;
int l = 1e7,r = 1e7; //l是队首,r是队尾
q[l] = s;
while(l <= r)
{
s = q[l]; l++;
vis[s] = 0; //标记出队
for(auto i : a[s])
{
if(dis[i.first] > dis[s]+i.second)
{
dis[i.first] = dis[s]+i.second;
if(!vis[i.first]) //没必要重复进队
{
vis[i.first] = 1;
q[--l] = i.first;
if(l < r && dis[q[l]] > dis[q[r]]) swap(q[l],q[r]);
}
}
}
}
}
参考博客
百度百科
https://www.cnblogs.com/Yangrui-Blog/p/8997721.html
https://www.cnblogs.com/dilthey/p/9583728.html