如何在有向加权图中找到负循环。我知道贝尔曼·福特算法是如何工作的，它告诉我是否存在可到达的负循环。但它没有明确命名。
如何获得循环的实际路径v1,v2,…vk,v1？
应用标准算法后，我们已经进行了 n−1 次迭代，并且不可能进一步改进。如果我们仍然可以降低到节点的距离，则存在负循环。
假设边 (v,u) 是贝尔曼福特算法在第 n 次迭代中失败的边 - d(u) > d(v) + w(v,u)。 所以我们知道 v,u 是负循环的一部分，但问题是我如何检测特定循环？
为了解决这个问题..我们使用贝尔曼福特算法。为了打印循环，我们将节点的父节点存储在向量（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;
}
假设边 (v,u) 是贝尔曼福特算法失败的边 在第 n 次迭代中 - d(u) > d(v) + w(v,u)。所以我们知道 v,u 是 负循环的一部分，但问题是我如何检测 具体周期？
在这种情况下，v、u 可能不是负循环的一部分。相反，由于存在负循环，在 Bellman-Ford 算法中放松边缘时，我们可以以较低的成本访问 u，因为负循环的 传出边缘可能会导致 u。在这种情况下，我们必须从u开始往回追溯，直到我们知道我们已经进入了这样一个循环。 答案中给出的代码指出但未能正确解释的是，通过保留父数组并在每次边缘松弛时标记每个节点的父节点，我们保证可以通过回溯来访问负循环父数组，直到找到相同的元素。通过保留已访问的布尔值数组，我们从 u 返回并继续使用已访问的父数组标记我们回溯的所有元素。当我们两次访问同一个节点时，我们将其标记为负循环的结束和开始，并开始插入我们访问的所有元素，同时回溯到我们的答案数组中，并且在回到负循环的开始/结束时，我们停止循环。即使 u 和 v 是负循环的一部分，这种方法也有效。 下面是我的 C++ 代码，并提供了注释（与之前的答案类似的代码）：
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n, m;
cin>>n>>m;// n is number of vertices, m is number of edges
vector<vector<int>> edges(m, vector<int>(3));
for(int i=0;i<m;i++){
int a, b, c;
cin>>a>>b>>c;
if(a==b && c<0){//if there is a self-loop, no need to apply the algorithm
cout<<"YES"<<endl<<a<<" "<<a<<endl;
return 0;
}
a--;//for converting to 0-based indexing
b--;
edges[i][0]=a;
edges[i][1]=b;
edges[i][2]=c;
}
vector<int> dist(n, 1e18);//initialising distances
vector<int> parents(n, -1);
for(int i=0;i<n-1;i++){//applying bellman-ford
for(int j=0;j<m;j++){
if(dist[edges[j][1]]>dist[edges[j][0]]+edges[j][2]){
parents[edges[j][1]]=edges[j][0];//updating parents
dist[edges[j][1]]=dist[edges[j][0]]+edges[j][2];//relaxing edges
}
}
}
int j;
for(j=0;j<m;j++){
if(dist[edges[j][1]]>dist[edges[j][0]]+edges[j][2]){//u and v found
cout<<"cycle exists"<<endl;
int cur=edges[j][0];
vector<bool> vis(n, false);
while(!vis[cur]){//backtracking till we find the same element twice
vis[cur]=true;
cur=parents[cur];
}
cout<<cur+1;//that element must be a part of the negative cycle
int stop=cur;//marking it as the end element
vector<int> ans;
cur=parents[cur];
while(cur!=stop){//backtracking and inserting all the elements in the answer array
ans.push_back(cur+1);
cur=parents[cur];
}
for(int i=ans.size()-1;i>=0;i--){//printing the cycle elements
cout<<" "<<ans[i];
}
cout<<" "<<stop+1<<endl;//printing the end element
break;
}
}
if(j==m){//if j==m, no additional relaxations can be done
cout<<"no cycle exists"<<endl;
}
return 0;
}
此外，尽管贝尔曼-福特算法是单源算法，但我们对其进行了修改，以有效检测任何负循环。这是因为所有具有负传出边的节点在该算法的第一次迭代中充当起始节点。由于任何负循环总是包含至少一个负边沿，因此这种边沿松弛方式有助于我们检测循环。