AOE网求最短路径的实验报告

《AOE网求最短路径的实验报告》需解决的的问题设计一个AOE网，并求出关键路径数据结构的定义typedefstructarcnode{intadjvex;//活动末端structarcnode*nexarc;doubleinfo;//活动持续时间}arcnode;typedefstructvnode{intdata;//事件名arcnode*fristarc;intdu;//A度}vnode;typedefstruct{intvexnum;//事件个数intactnum;//活动个数vnode*program;}AOE;程序的结构图输入事件数和活动数创建一个AOE网输入事件数和活动数创建一个AOE网求出关键路径程序结束函数的功能创建AOE网//建AOE网voidcreate(AOE*T){inti,start,end;doubletime;arcnode*p;T->program=(vnode*)malloc(T->vexnum*sizeof(vnode));if(!T->program) exit(0);for(i=0;i<T->vexnum;i++){T->program[i].data=i;T->program[i].du=0;T->program[i].fristarc=NULL;}printf("该项目的开始到结束在图中的点输入<i,j,info>\n");printf("如：4,5,9回车表示第四节点到第五节点之间的活动用了9个单位时间\n");for(i=0;i<T->actnum;i++){scanf("%d,%d,%lf”,&start,&end,&time);p=(arcnode*)malloc(sizeof(arcnode));p->adjvex=end-1;p->info=time;T->program[end-1].du++;p->nexarc=T->program[start-1].fristarc;T->program[start-1].fristarc=p;}}求关键路径〃找关键路径voidcrtical_activity(AOE*T){int*stack=(int*)malloc((T->vexnum+1)*sizeof(int));double*ve=(double*)malloc((T->vexnum)*sizeof(double));//诸存事件最早发生时间double*vl=(double*)malloc((T->vexnum)*sizeof(double));//储存事件最晚发生时间double*e=(double*)malloc((T->actnum)*sizeof(double));//储存活动最早开始时间double*l=(double*)malloc((T->actnum)*sizeof(double));〃储存活动最晚开始时间inti,j,k,top=0,bottom=0;arcnode*p;doublesumtime=0.0;for(i=0;i<T->vexnum;i++)ve[i]=0.0;for(i=0;i<T->vexnum;i++){if(T->program[i].du==0)stack[top++]=i;}while(top!=bottom){i=stack[bottom++];p=T->program[i].fristarc;while(p){k=p->adjvex;T->program[k].du-;if(T->program[k].du==0)stack[top++]=k;if(ve[k]<ve[i]+p->info)ve[k]=ve[i]+p->info;p=p->nexarc;}}sumtime=ve[T->vexnum-l];for(i=0;i<T->vexnum;i++)vl[i]=ve[T->vexnum-l];for(i=T->vexnum-l;i>=0;i-)intk=stack[i];p=T->program[k].fristarc;while(p)j=p->adjvex;if((vl[j]-p->info)<vl[k])vl[k]=vl[j]-p->info;p=p->nexarc;}}printf("|起点|终点|最早开始时间|最迟开始时间|差|判断|\n");i=0;for(j=0;j<T->vexnum;j++){p=T->program[j].fristarc;while(p){intk=p->adjvex;e[++i]=ve[j];l[i]=vl[k]-p->info;printf("|%4d|%4d|%lf|%lf|%lf|”,T->program[j].data+1,T->program[k].data+1,e[i],l[i],l[i]-e[i]);if(l[i]==e[i])printf("关键活动|\n");printf("\n");p=p->nexarc;}}printf('整个工程所用的最短时间为：%lf个单