用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期……
int SearchMapPath(vexnode* G,int prnum,int actnum,int& totaltime) //寻找关键活动 { int i,j,k,m=0; int front=-1,rear=-1; int*topologystack=(int*)malloc(prnum*sizeof(int));//用来保存拓扑排列 int*vl=(int*)malloc(prnum*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间
int*ve=(int*)malloc(prnum*sizeof(int));//用来表示Vj最早发生时间 int*l=(int*)malloc(actnum*sizeof(int));//用来表示活动Ai最晚发生时间 int*e=(int*)malloc(actnum*sizeof(int));//表示活动最早发生时间 edgenode *p; totaltime=0; for(i=0;i<prnum;i++) ve[i]=0; for(i=0;i<prnum;i++) { if(G[i].id==0) { topologystack[++rear]=i; m++; } } while(front!=rear) { front++; j=topologystack[front]; m++; p=G[j].link ; while(p) { k=p->adjvex ; G[k].id--; if(ve[j]+p->dut>ve[k]) ve[k]=ve[j]+p->dut ; if(G[k].id==0) topologystack[++rear]=k; p=p->next ; } } if(m<prnum) { printf("\n本程序所建立的图有回路不可计算出关键路径\n"); printf("将退出本程序\n"); return 0;