贝尔曼-福特算法中的 c++ 和分割错误 11

Question

我在C++中实现了贝尔曼-福特算法，以查找货币兑换问题中的负权重周期，当我放置一个测试用例时，它给出了

Segmentation Fault: 11

代码如下：

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
struct edge
{
int vertex;
double weight;
};
int mindist(int A[],bool B[],int n)
{
int v=0;
while(B[v]==true)
v++;
for(int i=v;i<n;i++)
{
if(B[i]==false)
if(A[i]<A[v])
v=i;
}
return v;
}
class Graph
{
public:
vector<edge> adj;
void add(int a,int b)
{
edge e;
e.vertex=a;
e.weight=b;
adj.push_back(e);
}
};
int main()
{
int n,m,u,v,j,isCycle=0;
double w;
edge temp;
cin>>n>>m;
Graph* G=new Graph[n];
for(int i=0;i<m;i++)
{
cin>>u>>v>>w;
w=-log(w);
G[u-1].add(v-1,w);
}
int* dist=new int[n];
bool* done = new bool[n];
for(int i=0;i<n;i++)
{
dist[i]= 10000;
done[i]=false;
}
dist[0]=0;
for(int i=0;i<n;i++)
{
j=mindist(dist,done,n);
done[j]=true;
for(int i=0;i<G[j].adj.size();i++)
{
temp=G[j].adj[i];
if(dist[temp.vertex]>temp.weight+dist[j])
dist[temp.vertex]=temp.weight+dist[j];
}
}
for(int i=0;i<n;i++)
{
temp=G[i].adj[i];
if(dist[temp.vertex]>temp.weight+dist[i])
{
isCycle=1;
break;
}
}
cout<<isCycle;
}

测试用例：(格式：- 第一顶点第二顶点权重(

注意，下面是一个有向图

10 9
1 2 1
6 7 1
8 9 1
9 10 1
3 4 1
7 8 1
4 5 1
5 6 1
2 3 1

我已经使用动态分配初始化了堆上的所有静态数组，但仍然收到相同的错误。谁能告诉我哪里出错了？

Answer 1

考虑一下当B都为真时会发生什么。

然后这个循环：

while(B[v]==true)
v++;

有未定义的行为，你很可能最终得到一个"在那里"的v。
然后返回v以下代码：

j=mindist(dist,done,n);
done[j]=true;
for(int i=0;i<G[j].adj.size();i++)

它将在外太空的某个地方写下，并查看不存在的Graph。

检查你的界限。

此外，在该部分中对两个嵌套循环使用i看起来很可疑。
即使这是您想要的，也可以重命名其中一个，以免看起来出错。

Answer 2

分割错误在第 70 行，因此在 G[i].adj[i] 中，adj[i] 不存在。每个调整点[i]的大小为1。此外，第 57 行的循环也是错误的，因为您在嵌套循环中也使用了 i。