BellmanFord 算法

第一个是创建一个图的代码，第二个是BellmanFord算法，内存泄露的问题大家轻拍

void ConstructGraph(Graph *G , char FilePath[]){
	FILE *f;
	f=fopen(FilePath,"r");
	char line[256];
	int num=0,weight=0,k=0,count=0,minus=0;
	fgets(line,256,f);
	count=atoi(line);//num of nodes
	G->vertexcount=count;
	G->graph=new Vertex[count]();
	for(int l=0,i=0,flag=0 ; fgets(line,256,f)!=NULL && l<count ; l++ ){//read one line
		for( i=0,flag=0,num=0 ; i<256 && line[i]; i++){
			if(line[i]==',' && flag++%2==1){
				if(minus)
					weight*=-1;
				minus=0;
				AdjVertex *temp=new AdjVertex(num,weight);
				temp->next=(G->graph)[l].adjvertexes;
				(G->graph)[l].adjvertexes=temp;//insert into l
				num=weight=0;
			}	
			if(line[i]=='-'){
				minus=1;
				continue;
			}    
			if(line[i]!=',' && flag%2==0)
				num=num*10+(line[i]-'0');
			if(line[i]!=',' && flag%2==1)
				weight=weight*10+(line[i]-'0');
		}
	}   	
	fclose(f);    
}

bool BellmanFord(Graph &g){
	for(int i=0 ; i<g.vertexcount ; i++){
		g.graph[i].id=i;
		g.graph[i].key=INT_MAX;
		g.graph[i].parent=-1;
	}
	g.graph[0].key=0;
	AdjVertex *p;
	int id,weight;
	for(int j=1 ; j<g.vertexcount ; j++){
		for(int i=0 ; i<g.vertexcount ; i++){
			p=g.graph[i].adjvertexes;
			for( ; p ; p=p->next){
				id=p->id;
				weight=p->weight;
				if(g.graph[id].key>g.graph[i].key+weight){
					g.graph[id].key=g.graph[i].key+weight;
					g.graph[i].parent=id;
				}
			}    
		}
	}
	for(int i=0 ; i<g.vertexcount ; i++){
		p=g.graph[i].adjvertexes;
		for( ; p ; p=p->next ){
			id=p->id;
			weight=p->weight;
			if(g.graph[id].key>g.graph[i].key+weight)
				return false;
		}
	}
	return true;
}

给出所有的定义的数据结构

struct AdjVertex{
	int id;
	int weight;
	AdjVertex *next;
	AdjVertex():id(-1),weight(0),next(NULL){}
	AdjVertex(int vid,int ew):id(vid),weight(ew){}
};

struct Vertex{
	int id;
	int key;
	int parent;
	AdjVertex * adjvertexes;
	Vertex():id(-1),key(INT_MAX),parent(-1),adjvertexes(NULL){}
};

struct Graph{
	int vertexcount;
	Vertex* graph;
};