gjpath.c

数据结构--c语言

void criticalpath(aoelgrath dig,int n)
{
	int i,j,k,m,front,rear;
	int ve[mvnum],vl[mvnum],e[mvnum],l[mvnum];
	int tpord[mvnum];
	edgenode *p;
	for(i=1;i<=n;i++)
		ve[i]=0;
	front=0;rear=0;
	for(i=1;i<=n;i++)
	{
		if(dig[i].id==0)
		{
			rear++;
			tpord[rear]=i;
		}
	}
	m=0;
	while(front!=rear)
	{
		front++;j=tpord[front];
		m++;
		p=dig[j].link;
		while(p!=NULL)
		{
			k=p->adjvex;
			dig[k].id=dig[k].id-1;
			if(ve[j]+p->dut>ve[k])
				ve[k]=ve[j]+p->dut;
			if(dig[k].id==0)
			{
				rear++;tpord[rear]=k;
			}
			p=p->next;
		}
	}
	if(m<n){
		printf("aoe网有回路\n");
		return;
	}
	for(i=1li<=n;i++)
		vl[i]=ve[i];
	for(i=n-1;i>=1;i--)
	{
		j=tpord[i];
		p=dig[j].link;
		while(p!=NULL)
		{
			k=p->adjvex;
			if(vl[k]-p->dut>vl[j])
				vl[j]=vl[k]-p->dut;
			p=p->next;
		}
	}
	i=0;
	for(j=1;j<=n;j++)
	{
		p=dig[j].link;
		while(p!=NULL)
		{
			k=p->adjvex;i++;
			e[i]=ve[j];l[i]=vl[k]-p->dut;
			printf("顶点v%d到顶点v%d ",dig[j].vertex,dig[k].vertex);
			if(l[i]==e[i])
				printf("是关键活动\n");
			else
				printf("不是关键活动\n");
			p=p->next;
		}
	}
}