SPFA学习笔记

介绍

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

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

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

实现

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

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 = first[i]; i; i = ed[i].next) {  //从当前点的第一条出边开始枚举
            int e = ed[i].e;
            if(d[e] > d[now] + ed[i].d) {  //进行松弛
                d[e] = d[now] + ed[i].d;
                if(!inq[e]) {  //如果被更改的出边指向的点不在队列中，将其入队
                    q.push(e);
                    inq[e] = true;
                }
            }
        }
    }
}