SPFA: Shortest Path Faster Algorithm

看到名字不禁为之一颤，SPFA算法是西南交通大学段凡丁于1994年发表的。

SPFA 也是竞赛中最常见的算法之一，不仅仅用来解决带负权的单源最短路

而且是求解差分约束问题的专用算法，也常用它和最大流合作解决最小费问题

SPFA 算法的最坏复杂度为 O(2*E)。。

SPFA 和dijkstra 格式很接近，只是加了个队列或栈就变得无比神奇了。

这里用邻接表形式写下spfa 的模板

后面再介绍它的其它功能，这里只知道它处理最短路很快即可

优点
可以处理负权，判负环，快
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
queue<int> q;
int spfa(int s,int t){
    memset(d,0x3f,sizeof(d));
    memset(in,0,sizeof(vis));
    //memset(c,0,sizeof(c));
    q.push(s);
    in[s]=1;
    //c[s]=1;
    while(!q.empty()){
        int k=q.front();q.pop();
        in[k]=0;
        for(int i=head[k];i!=-1;i=e[i].nxt)if(d[k]+e[i]<d[i]){
            d[i]=e[i].w+d[k];
            if(!in[e[i].t]){
                q.push(e[i].t);
                in[e[i].t]++;
                c[e[i].t]++;
                //if(c[e[i].t]>n)return ok=0 
            }
        }
    }
}