2

如何在有向加权图中找到负循环。我知道 Bellman Ford 算法是如何工作的，并且它告诉我是否存在可达到的负循环。但它没有明确命名它。

如何获得循环的实际路径 v1,v2,...vk,v1？

应用标准算法后，我们已经进行了 n-1 次迭代，应该不可能有进一步的改进。如果我们仍然可以降低到节点的距离，则存在负循环。

假设边 (v,u) 是贝尔曼福特算法在第 n 次迭代中失败的边 - d(u) > d(v) + w(v,u)。所以我们知道 v,u 是负循环的一部分，但问题是我如何检测特定循环？

4

1 回答 1

0

为了解决这个问题..我们使用 bellman-ford 算法。为了打印循环，我们将节点的父节点存储在向量（par）中。也可以有多个循环，所以在第 N 次迭代中我们找到 -ve 循环。因此，我们创建一个访问数组并转到循环的开始，而不是使用 par（父向量），我们可以找到循环的路径。我的代码可以帮助你

#include <bits/stdc++.h>
#include <iostream>
using namespace std; 
#define ll long long 
int main(){
    int n,m;
    cin>> n>>m;
    vector<vector<pair<int,ll int > >>graph(n+1);
    for(int i=0;i<m;i++){
       ll int a,b,c;
       cin>> a>> b>> c;
       graph[a].push_back({b,c});
    }

    vector<ll int >dist(n+1,1e14),par(n+1,-1);

    // applying bellman ford algo.

    for(int i=1;i<n;i++){
       for(int j=1;j<=n;j++){
           for(auto k:graph[j]){
                ll int node=k.first,c=k.second;
                if(dist[node]>c+dist[j]){
                    dist[node]=c+dist[j];
                    par[node]=j;
                }
           }
       }
    }


    // checking nth iteration 


    bool flag=false;
    for(int i=1;i<=n;i++){
       for(auto k:graph[i]){
          ll int node=k.first,c=k.second;
          if(dist[node]>c+dist[i]){
             dist[node]=c+dist[i];
             par[node]=i;
             flag=true;
          }
            
          if(flag){

            // negative cycle founded
            
            cout<<"YES cycle founded"<<endl;

            vector<int >ans;
            vector<bool>vis(n+1,false);


            //  loop for finding the start of cycle
            while(!vis[i]){
                vis[i]=true;
                i=par[i];
            }

            
            // pushing the nodes of path in vector(ans).

            int u=i;
            ans.push_back(u);
            u=par[u];
            while(u^i){
                ans.push_back(u);
                u=par[u];
            }
            ans.push_back(u);
            reverse(ans.begin(),ans.end());


            //printing path

            for(auto z:ans)cout<<z<<" ";
            return 0;
            }
       }
    }   

    if(!flag)cout<<"NO cycle founded"<<endl;
}

问题链接- https://cses.fi/problemset/task/1197/

于 2020-07-14T14:58:51.983 回答