criticalpath.cpp

有关关键路径的算法源代码

#include <stdio.h>
#include <malloc.h>
#define M 20
#define MAX 100
typedef struct node   //表结点
{   int vex;
    int dur;        //活动的持续时间
	int act;        //存放活动的编号
    struct node *next;
}JD;
typedef struct tnode    //头结点
{   int vexdata;
    int in;
    struct node *link;
}TD;


int crt_linklist(TD g[])    // 输入顶点和弧信息，建立其邻接表
{   int n,e,i,j,k,dur,m=1;
    JD *p;
    printf("Input the number of node,arc:");
    scanf("%d,%d",&n,&e);
    for(i=1;i<=n;i++)
    {  g[i].vexdata=i;
       g[i].in=0;
       g[i].link=NULL;
    }
    for(k=1;k<=e;k++)
    {   printf("i,j,dur:");
	scanf("%d,%d,%d",&i,&j,&dur);
	p=(JD *)malloc(sizeof(JD));
	p->vex=j;
	p->dur=dur;
	p->act=m;
	m++;
	p->next=g[i].link;
	g[i].link=p;
    }
    return(n);
}

void cal_in(TD g[],int n)    //计算各顶点入度
{  int i,k;
   JD *p;
   for(i=1;i<=n;i++)
   {  p=g[i].link;
      while(p!=NULL)
      {  k=p->vex;
	 g[k].in++;
	 p=p->next;
      }
   }
}


int toporder(TD g[],int n,int ve[],int top2[],int *t2) // 进行拓扑排序，求顶点的ve[i]
{  int top1[M];
   int m,k,j,top;
   JD *p;
   top=0; m=0;
   for(j=1;j<=n;j++)
      ve[j]=0;
   for(j=1;j<=n;j++)
     if(g[j].in==0)
     {  top1[top]=j;
	top++;
     }
   while(top>0)
   {  j=top1[--top];
      top2[*t2]=j;
      (*t2)++;
      m++;
      p=g[j].link;
      while(p!=NULL)
      {  k=p->vex;
	 g[k].in--;
	 if(g[k].in==0)
	    top1[top++]=k;
	 if(ve[j]+p->dur>ve[k])
	    ve[k]=ve[j]+p->dur;
	 p=p->next;
      }
   }
   if(m<n)  return(0);
   else     return(1);
}

void critical_path(TD g[],int n)    //计算每条弧(活动)的e[i]和l[i],找出e[i]=l[i]的关键活动
{   int i,t2=0,j,k,ee,el;
    char tag;
    JD *p;
    int ve[M],vl[M],top2[M];
    i=toporder(g,n,ve,top2,&t2);
    if(!i)
       printf("Has a cycle!");
    else
    {  for(i=1;i<=n;i++)
	  vl[i]=MAX;
       vl[n]=ve[n];
       while(t2>0)
       {  j=top2[--t2];
	  p=g[j].link;
	  while(p!=NULL)     //按逆拓扑序列求顶点的vl[j]
	  {  k=p->vex;
	     if(vl[k]-p->dur<vl[j])
		  vl[j]=vl[k]-p->dur;
	     p=p->next;
	  }
       }
       for(j=1;j<=n;j++)
       {  p=g[j].link;
	  while(p!=NULL)
	  {  k=p->vex;
	     ee=ve[j];
	     el=vl[k]-p->dur;
	     if(ee==el)
		 tag='*';
	     else
		 tag=' ';
	     printf("Vt=%d,Vh=%d,dur=%d,act=%d,ee=%d,el=%d,%c\n",j,k,p->dur,p->act,ee,el,tag);
	     p=p->next;
	  }
       }
    }
}

void main()
{  int n;
   TD g[M];
   n=crt_linklist(g);
   cal_in(g,n);
   critical_path(g,n);
}