关键路径
#include <stdio.h>
#include <malloc.h>
#define M 20
#define MAX 100
typedef struct node
{ int vex;
int length;
struct node *next;
}JD;
typedef struct tnode
{ int vexdata;
int in;
struct node *link;
}TD;
int loc_vertex(TD g[],int vex,int n) //定位输入结点的存储坐标
{ int i,j;
for(i=1;i<=n;i++)
if(g[i].vexdata==vex)
return(i);
return(0);
}
int crt_linklist(TD g[]) //建立邻接链表
{ int n,e,i,j,k,vt,vh,length;
JD *p;
printf("Input and the number of node,arc:");
scanf("%d,%d",&n,&e);
for(i=1;i<=n;i++) //输入结点的信息
{ printf("g[%d].vexdata=",i);
scanf("%d",&g[i].vexdata);
g[i].in=0;
g[i].link=NULL;
}
for(k=1;k<=e;k++) //输入边的信息
{ printf("Vt,Vh,length:");
scanf("%d,%d,%d",&vt,&vh,&length);
i=loc_vertex(g,vt,n);
j=loc_vertex(g,vh,n);
p=(JD *)malloc(sizeof(JD));
p->vex=j;
p->length=length;
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 dut(TD g[],int vt,int vh) //返回每个结点之间的边的权值
{ JD *p;
p=g[vt].link;
while(p!=NULL)
{ if(p->vex==vh)
return(p->length);
else
p=p->next;
}
return(MAX);
}
int toporder(TD g[],int n,int ve[],int top2[],int *t2) //作用在于求ve[k]，和为后面的求vl[k]
{ int top1[M];
int m,k,j,top;
JD *p;
top=0; m=0;
for(j=1;j<=n;j++) //初始化事件（结点）的最早开始时间,方法二：memset(ve,0,sizeof(ve));
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初值为零
(*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]+dut(g,j,k)>ve[k]) //求ve[k]，ve[k]=ve[j]+dut(g,j,k)；（ve[1]=0;）
ve[k]=ve[j]+dut(g,j,k);
p=p->next;
}
}
if(m<n) return(0);
else return(1);
}
void critical_path(TD g[],int n)
{ 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[k]*///
vl[n]=ve[n];
while(t2>0)
{ j=top2[--t2];
p=g[j].link;
while(p!=NULL)
{ k=p->vex;
if(vl[k]-dut(g,j,k)<vl[j])
vl[j]=vl[k]-dut(g,j,k);
p=p->next;
}
}
///* 求出活动的的e[k],l[k]*///
for(j=1;j<=n;j++)
{ p=g[j].link;
while(p!=NULL)
{ k=p->vex;
ee=ve[j];
el=vl[k]-dut(g,j,k);
if(ee==el)
tag='*';//表示关键路径
else
tag=' ';
printf("Vt=%d,Vh=%d,Length=%d,ee=%d,el=%d,%c\n",j,k,dut(g,j,k),ee,el,tag);
p=p->next;
}
}
}
}
int main()
{ int n;
TD g[M];
n=crt_linklist(g);
cal_in(g,n);
critical_path(g,n);
return (0);
}