Day3 | Hope_Y's blog

上一天了解了Dijkstra算法和Floyd两大最短路算法，但是如果图中有负环，那么每次更新就不会对了，那么我们需要另一个特殊的算法SPFA算法。

$SPFA$算法的全称就是Shortest Path Faster Algorithm，但是，在某些大型场合会被万恶的出题人卡掉~~（丧心病狂）~~，但是对于稀疏图和判断负环，这个算法的优越性还是有的。复杂度为$O(ke)$$(k \le 2)$，比Dijikstra和Floyd算法要低很多。

所谓负环，就是边权和为负数的环。

我们知道，一般情况下，图上的最短路都是确定的。但是一旦图上有一个负环，$s$到$t$的最短路就会不远千里的去覆盖上这个环（只要能够到达），并且不厌其烦的走上一遍又一遍。由于负环的边权和是负的，并且它是一个环，也就是说走一遍和走无数遍都停留在进入的那个点。那么最短路每经过一次这个负环，这个费用都会缩小一点，如果经过了无数次，也就是无穷小，也就是不存在最短路。当然这里有一个限定，就是每个点经过的次数不能超过$1$次。

$SPFA$与$Dijkstra$算法的主要区别就是一个是用$dfs$的方式来松弛操作，将dfs改成bfs之后，再来个计数操作判断负环。

$SPFA$的判定方式就是不断地收紧每个点到起点的最短路径，每次都不一定会收到最紧，但只要有解，最终一定会收成最紧（这也正是它这么好卡的原因，一点一点的，能不慢吗）。我们前面提到过，如果存在负环，那么最短路会不断缩小至无穷小。那么这里我们就可以应用它的这一特点。在$SPFA$中，每个点最短被其他$n−1$个点各收紧一次，如果被收紧了$n$次，显然是不合理的。那么我们就记录每个点被收紧的次数，有任何点超过$n$次，就可以判定存在负环了，如果$SPFA$成功运行完了，就证明不存在负环。

来个例题康康吧

HDU-2066

题意：有T条路径，S个起点，D个终点，问你$S_i$到$D_j$最短路径是多少。

题解：对于每个$S_i$都跑一遍最短路就好了（这里直接用dijkstra也可以的）。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
const int inf = 0x3f3f3f3f;
vector<pair<int,int>>E[maxn];
int dis[maxn],inq[maxn],num[maxn];
void init(){
    for(int i=0; i<maxn; i++){
        E[i].clear();
        inq[i]=0;
        dis[i]=inf;
        num[i]=0;
    }
}
bool SPFA(int s,int n){
    queue<int>q;
    dis[s]=0;
    q.push(s);
    inq[s]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        inq[now]=0;
        num[now]++;
        for(int i=0; i<(int)E[now].size(); i++){
            int val=E[now][i].second;
            int j=E[now][i].first;
            if(dis[j]>dis[now]+val){
                dis[j]=dis[now]+val;
                if(!inq[j]){
                    q.push(j);
                    inq[j]=1;
                    num[j]++;
                    if(num[j] > n) return false;
                }
            }
        }
    }
    return true;
}
int a[maxn],b[maxn];
int main(){
    int t,s,d,n;
    while(~scanf("%d %d %d",&t,&s,&d)){
        init();
        for(int i=0; i<t; i++){
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            n=max(n,x);
            n=max(n,y);
            E[x].push_back(make_pair(y,z));
            E[y].push_back(make_pair(x,z));
        }
        for(int i=0; i<s; i++) scanf("%d",&a[i]);
        for(int i=0; i<d; i++) scanf("%d",&b[i]);
        int ans=inf;
        for(int i=0; i<s; i++){
            SPFA(a[i],n);
            for(int j=0; j<d; j++) ans=min(ans,dis[b[j]]);
        }
        printf("%d\n",ans);
    }
}

再来看看一个直接判断负环的题目

P3385 【模板】负环

题意：一个n，m。n代表n个点，m代表m条边，当边权为正表示双向边，否则为单向，求是否有负环。

有负环输出”YE5”，否则输出”N0”，来自出题人满满的恶意，YE5最后一个字符是5，N0最后一个字符是0

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
const int inf = 0x3f3f3f3f;
vector<pair<int,int> >E[maxn];
int dis[maxn],inq[maxn],num[maxn];
void init(){
    for(int i=0; i<maxn; i++){
        E[i].clear();
        inq[i]=0;
        dis[i]=inf;
        num[i]=0;
    }
}
bool SPFA(int s,int n){
    queue<int>q;
    dis[s]=0;
    q.push(s);
    inq[s]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        inq[now]=0;
        num[now]++;
        for(int i=0; i<(int)E[now].size(); i++){
            int val=E[now][i].second;
            int j=E[now][i].first;
            if(dis[j]>dis[now]+val){
                dis[j]=dis[now]+val;
                if(!inq[j]){
                    q.push(j);
                    inq[j]=1;
                    num[j]++;
                    if(num[j] > n) return false;
                }
            }
        }
    }
    return true;
}
int main(){
    int n,m,T;
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d %d",&n,&m);
        for(int i=0; i<m; i++){
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            E[x].push_back(make_pair(y,z));
            if(z>=0) E[y].push_back(make_pair(x,z));
        }
        if(SPFA(1,n)) puts("N0");
        else puts("YE5");
    }
}