单源最短路问题

spfa算法

spfa:每次取队列头的点,对于每一个出边松弛,如果松弛到一个没在队列里的点则将它入队。
spfa判负环:如果存在一个点,入队的次数超过点数n,那么存在负环。
dfs:枚举出边进行松弛,对于没有遍历过的点进行递归,继续向下松弛。
dfs判负环:如果松弛到一个已经走过的点,那么存在负环。


spfa的优秀就在于随机图下的极优时间复杂度,相比于dijkstra,spfa的应用也更为广泛,可以在存在负边权的图中求解最短路。但是由于过于简单暴力,这个算法非常容易被卡,复杂度退化.


SPFA板子:

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#define N 110000
#define M 110000
using namespace std;
int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
struct node{
    int to,tar;
    node *nxt;
}table[M],*head[N];
queue<int>Q;
int tot=2,n,m,S,T;
void ins(int x,int y,int z){
    table[tot].to=y;
    table[tot].tar=z;
    table[tot].nxt=head[x];
    head[x]=&table[tot++];
    return;
}
int dis[N],don[N];
bool vis[N];
void init(){
    tot=2;
    memset(dis,0x3f,sizeof(dis));dis[S]=0;
    memset(don,0,sizeof(don));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n;i++)head[i]=NULL;
    while(!Q.empty())Q.pop();
    return;
}
bool spfa_bfs(){
    Q.push(S);
    dis[S]=0;
    vis[S]=1;
    don[S]=1;
    while(!Q.empty()){
        int t=Q.front();Q.pop();vis[t]=false;
        for(node *i=head[t];i!=NULL;i=i->nxt){
            if(dis[i->to]>dis[t]+i->tar){
                dis[i->to]=dis[t]+i->tar;
                if(!vis[i->to]){
                    Q.push(i->to);
                    vis[i->to]=true;
                    don[i->to]++;
                    if(don[i->to]>n){
                        return false;
                    }
                }
            }
        }
    }
    return true;
}
bool spfa_dfs(int x){
    vis[x]=true;
    for(node *i=head[x];i!=NULL;i=i->nxt){
        int t=i->to;
        if(dis[t]>dis[x]+i->tar){
            dis[t]=dis[x]+i->tar;
            if(!vis[t]){
                if(spfa_dfs(t))
                    return true;
            }
            else
                return true;
        }
    }
    vis[x]=false;
    return false;
}
int main()
{
    while(1){
        n=rd();m=rd();S=n;T=1;
        if((!n)&&(!m))return 0;
        init();
        for(int i=0;i<m;i++){
            int a=rd(),b=rd(),c=rd();
            ins(a,b,c);
            ins(b,a,c);
        }
        spfa_dfs(S);
        printf("%d\n",dis[T]);
    }
    return 0;
}


血まみれからの方がさ,勝つ時にはカッコイイだろう.