aoe.cpp

关键路径的实现算法 用到文件管理 C++编写 可用做课程设计

#include <fstream>
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
const int  MaxValue=20;
struct edgenode
{
	int adjvex;
	int weight;
	edgenode* next;
};


void KeyPath(edgenode*GL[],int n)
{
int i,j,k,top,q=0;
edgenode* p=NULL;
int *v=new int[n];//用来记录扩普排序的结果
int *ve=new int[n];//用来记录每个顶点的最早发生时间
int *vl=new int[n];//用来记录每个顶点的最迟发生时间
int *d=new int[n];//用来统计每个顶点的入度
for(i=0;i<n;i++)
{
	d[i]=0;
}
for(i=0;i<n;i++)
{
	p=GL[i];
	while(p!=NULL)
	{
		j=p->adjvex;
		d[j]++;
		p=p->next;
	}
}
top=-1;
for(i=0;i<n;i++)
if(d[i]==0)
{
	d[i]=top;
	top=i;
}
while(top!=-1)
{
	j=top;
	top=d[top];
	v[q++]=j;
	p=GL[j];
	while(p!=NULL)
	{
		k=p->adjvex;
		d[k]--;
		if(d[k]==0)
		{
			d[k]=top;
			top=k;
		}
		p=p->next;
	}
}

for(i=0;i<n;i++) //每个事件最早发生时间初始化为0
	ve[i]=0;
for(i=0;i<n;i++)
{
	j=v[i];
	p=GL[j];
	while(p!=NULL)
	{
		k=p->adjvex;
		if(ve[k]<ve[j]+p->weight)
			ve[k]=ve[j]+p->weight;
		p=p->next;
	}
}

int h=0;
for(h=0;h<n;h++)
{
cout<<ve[h]<<"-";
}
cout<<endl;
for(i=0;i<n;i++) //每个事件最迟发生时间初始化为ve[n-1]
	vl[i]=ve[n-1];
for(i=n-1;i>=0;i--)
{
	j=v[i];
	p=GL[j];
	while(p!=NULL)
	{
		k=p->adjvex;
		if(vl[j]>vl[k]-p->weight)
			vl[j]=vl[k]-p->weight;
		p=p->next;
	}
}
for(h=0;h<n;h++)
{
cout<<vl[h]<<"-";
}
cout<<endl;
cout<<"关键路径为： "<<endl;
for(i=0;i<n;i++)
	if(ve[v[i]]==vl[v[i]])
		cout<<"v"<<v[i]<<" ";
}

void main()
{
	int iNodeNum,iPathNum,i,j,w;
int m=0;
	edgenode*GL[MaxValue];
	//edgenode **GL=new *edgenode;
	for(m=0;m<MaxValue;m++)
	{
	GL[m]=new edgenode;
	}
//*GL=new edgenode[MaxValue];
for( m=0;m<MaxValue;m++)
{
GL[m]=NULL;
}
//	edgenode **GL=new *edgenode;
//	*GL=new edgenode[MaxValue];

	edgenode* p;
	ifstream infile;
	//	char test[20];
		char strNodeNum[10];
		char strPathNum[10];
		char stri[5];
		char strj[5];
		char strw[5];

	infile.open("graph.txt",ios::in);
	if(infile.rdstate()==ios_base::badbit)	
		cerr<<" "<<endl;
	else 
	{
		//infile>>test;
		infile.getline(strNodeNum,10);
		infile.getline(strPathNum,10);
iPathNum=atoi(strPathNum);
iNodeNum=atoi(strNodeNum);
		cout<<strNodeNum<<"  "<<strPathNum<<endl;
	//	infile>>NodeNum>>'\n';
	//	infile>>PathNum>>'\n';
		for(int m=0;m<iPathNum;m++)
		{
	//		infile>>i>>" ">>j>>" ">>w>>'\n';
			infile.getline(stri,5,' ');
			infile.getline(strj,5,' ');
			infile.getline(strw,5);
			cout<<stri<<" "<<strj<<"  "<<strw<<endl;
i=atoi(stri);
j=atoi(strj);
w=atoi(strw);
/*
p=new edgenode;
p->adjvex=j;
p->weight=w;
p->next=GL[i]->next;
GL[i]->next=p;
*/


			p=new edgenode;
			p->adjvex=j;
			p->weight=w;
			p->next=GL[i];
			GL[i]=p;
			
		}
		infile.close();
	}

KeyPath(GL,iNodeNum);
return;
}