SPFA学习笔记

SPFA学习笔记

介绍

SPFA(Shortest Path Faster Algorithm)就是队列优化的Bellman-Ford,时间复杂度声称可以优化到$O(km)$,实际很容易卡到最坏的情况$O(nm)$,可以处理负权边,判定负权环。建议除非有负权边,否则不要用SPFA。

Bellman-Ford的思想是对整张图进行$n-1$次松弛,每次枚举每条边进行松弛,最后一定能得出最优解,而SPFA使得在上述过程中避免了无意义的松弛。只有成功的松弛操作才会对那个点产生影响,所以使用队列维护等待松弛的点,每次取出一个点进行松弛,对于所有松弛成功的点加入队列。

如果某个点松弛了$n$次,则说明图中一定有负环。

实现

存图代码请看文末链接文章中的Dij笔记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int MAXN = 100010;
const int MAXM = 200010;

bool inq[MAXN]; //inq[i]标记点i是否入队
queue<int> q; //定义队列q保存等待更新的点

inline void spfa(int s) { //s为起点
q.push(s); //将点s加入等待更新到队列
inq[s] = true; //打上入队标记
memset(d,0x3f,sizeof(d)); //将起点到点i的最短距离d[i]初始化为INF
d[s] = 0; //使起点到起点到距离为0
while(!q.empty()) {
int now = q.front(); q.pop(); //取出队列中的一个点
inq[now] = false; //取消入队标记
for(int i = he[now]; i; i = ne[i]) { //从当前点的第一条出边开始枚举
Edge& e = ed[i];
if(d[e.to] > d[now] + e.dist) { //进行松弛
d[e.to] = d[now] + e.dist;
if(!inq[e.to]) { //如果被更改的出边指向的点不在队列中,将其入队
q.push(e.to);
inq[e.to] = true;
}
}
}
}
}

相关文章

Dijkstra学习笔记 | Ender’s blog

Floyd学习笔记 | Ender’s blog

感谢支持,您的支持将是我原创的动力!