这算是我的第一篇使用LaTeX的文章
易写,支持负权,可判负环,可以求最短路,也可以最长路,什么都行。就是容易被卡qwq
所以SPFA他死了。是Bellman_Ford算法的队列优化版。
使用范围
支持负权,可以处理负环,可判负环,可以求最短路,也可以求最长路。
平均时间复杂度 \(O(m)\),极限时间复杂度为 \(O(nm)\) 即退化成 Bellman_Ford。
如上面所说,容易被卡成 \(O(nm)\) 的时间复杂度。
中心思想
其算法正确性来自 Bellman_Ford 算法。
观察 Bellman_Ford 算法,可以发现,实际上只有上次被松弛的点,才能有可能引起下次操作中边的松弛,于是可以用一个队列,存入“可能引起下次松弛的点”,只利用这里面的点即可。
值得注意的是,这个队列中的点不需要重复,它并没有意义,所以对于上面所说的点,我们要判断是否在队列之内。
代码
给出两种代码,一种手写循环队列,一种用 SLT 队列。
如果不用 STL 队列,一定要手写队列,因为一个点可能会入队多次,如果不循环,可能会出界。因此手写要用循环队列。是手写还是直接 STL 就看个人习惯了。
值得一说的特性,因为 \(st\) 数组内存的是每个点是否进队,而当 SPFA 结束时,队列里一定没有点,因此 \(st\) 数组全为空。
循环队列
int spfa(int S, int T)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
int tt = 0, hh = 0;
q[tt ++ ] = S;
dist[S] = 0;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false; // 退出队列后还有可能进来
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 保证队列中这个点只有一个
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return dist[T];
}
STL 队列
int spfa(int S, int T)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
queue<int> q;
q.push(S);
dist[S] = 0;
st[S] = true; // 这句话可有可无,毕竟入队之后直接就 st[t] = false; 了
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (st[j] == 0)
{
st[j] = true;
q.push(j);
}
}
}
}
return dist[T];
}
扩展
- SPFA判断负环