AcWing 851. spfa求最短路&&AcWing 852. spfa判断负环—spfa算法

2024-01-07 19:57:12

问题链接:AcWing 851. spfa求最短路
问题描述
在这里插入图片描述
spfa算法是对bellman-ford算法的改进,bellman-ford算法比较笨,要遍历所有边来更新,其实如果当前点没有被更新的话,就不用用当前点来更新他所连接的点了。我们只需要每次更新一个点后,继续更新该点连接的点即可。
代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=1e5+10,INF=0x3f3f3f3f;

struct E{
    int v,w,nxt;
};
E edge[M];
int head[N], idx=0;
int n,m;
int dist[N];
int st[N];

void init(){
    for(int i=0;i<=n;i++){
        head[i]=-1;
        dist[i]=INF;
    }
}
void add(int u,int v,int w){
    edge[idx].v=v;
    edge[idx].w=w;
    edge[idx].nxt=head[u];
    head[u]=idx++;
}
int spfa(){
    dist[1]=0;
    st[1]=1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=head[t];~i;i=edge[i].nxt){
            int v=edge[i].v;
            int w=edge[i].w;
            if(dist[v]>dist[t]+w){
                dist[v]=dist[t]+w;
                if(!st[v]){
                    q.push(v);
                    st[v]=1;
                }
            }
        }
    }
    return dist[n];
}
int main(){
    cin>>n>>m;
    init();
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    int k=spfa();
    if(k<INF/2) cout<<k;
    else puts("impossible");
    return 0;
}

我这里用的是链式前向星来存图
问题链接:AcWing 852. spfa判断负环
问题描述
在这里插入图片描述
正如bellman-ford算法中提到的,一个点到其余点的最短路径,最长需要经过n-1条边,所以如果有大于等于n条边,则说明一定有环。注意从单元点出发,有可能找不到环,因为环不一定在最短路径上。
代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=1e5+10,INF=0x3f3f3f3f;

struct E{
    int v,w,nxt;
};
E edge[M];
int head[N], idx=0;
int n,m;
int dist[N];
int st[N];
int cnt[N];

void init(){
    for(int i=0;i<=n;i++){
        head[i]=-1;
        dist[i]=INF;
    }
}
void add(int u,int v,int w){
    edge[idx].v=v;
    edge[idx].w=w;
    edge[idx].nxt=head[u];
    head[u]=idx++;
}
bool spfa(){
    dist[1]=0;
    queue<int> q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    } 
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=head[t];~i;i=edge[i].nxt){
            int v=edge[i].v;
            int w=edge[i].w;
            if(dist[v]>dist[t]+w){
                cnt[v]=cnt[t]+1;
                if(cnt[v]>=n) return false;
                dist[v]=dist[t]+w;
                if(!st[v]){
                    q.push(v);
                    st[v]=1;
                }
            }
        }
    }
    return true;
}
int main(){
    cin>>n>>m;
    init();
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    int k=spfa();
    if(!k) puts("Yes");
    else puts("No");
    return 0;
}

文章来源:https://blog.csdn.net/qq_43851311/article/details/135426797
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。