算法基础课之SPFA判断负环

2023-12-17 22:30:40

SPFA判断负环

  • 核心思想:spfa算法 当遍历一个点时 cnt数组记录边数 若有负环 边数会无限+1 cnt>=n是即为有负环

    •   #include<iostream>
        #include<cstring>
        #include<algorithm>
        #include<queue>
        
        using namespace std;
        const int N = 2010 , M = 10010;
        
        int h[N], e[M] , ne[M] , w[M] , idx;
        int d[M] , cnt[N];
        int n,m;
        bool st[N];
        
        void add(int a,int b,int c)
        {
            e[idx] = b;
            ne[idx] = h[a];
            w[idx] = c;
            h[a] = idx++;
        }
        
        bool spfa()
        {
            //不用初始化d,只要确定d更新了即可
            queue<int> q;  
            for(int i=1;i<=n;i++)
            {
                st[i] = true;
                q.push(i);  //把每个点都放进去 因为不一定是从1开始的回路 如果不放:从1开始的回路就找不到了?
            }
            
            while(q.size())
            {
                int t = q.front();
                q.pop();
                
                st[t] = false;
                
                for(int i = h[t]; i!=-1 ;i = ne[i])
                {
                    int j = e[i];
                    
                    if(d[j] > d[t] + w[i])
                    {
                        d[j] = d[t] + w[i];
                        cnt[j] = cnt[t] + 1 ;  
                        
                        if(cnt[j] >= n) return true;  //找到回路
                        
                        if(!st[j])
                        {
                            q.push(j);
                            st[j] = true;
                        }
                    }
                }
            }
            return false;
        }
        
        int main(){
            cin>>n>>m;
            
            memset(h,-1,sizeof h);
            while(m--)
            {
                int a,b,c;
                cin>>a>>b>>c;
                add(a,b,c);
            }
            
            if(spfa()) puts("Yes");
            else puts("No");
            
        }
      

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