数据结构求关键路径实习报告(2)

用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期……

<i,j>S, 1<=i<=n-1

其中，S是所有以i为弧尾的弧的集合。

两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。 3.2 算法步骤

(1)输入e条弧<j,k>，建立AOE网的存储结构。

(2)从源点v1出发，令ve(1)=0,按拓扑有序求其余各顶点的最早发生时间ve(i)（2<=i<=n）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3。

(3)从汇点vn出发，令vl(n)=ve(n),求 按逆拓扑有序求其余各顶点的最迟发生时间vl(i)（1<=i<=n-1）。

(4)根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，若某条弧满足条件e(s)=l(s)，则为关键活动。 4．程序流程图

用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期……

三、程序清单

#include<stdio.h> #include<stdlib.h> #include<iomanip.h> #include <process.h>

typedef struct node //定义表结点 { int adjvex; //该弧所指向的顶点的位置 int dut; //弧的权值 struct node *next; //指向下一条弧的指针 }edgenode;

typedef struct //定义头结点 { int projectname; //顶点信息 int id; //结点入度 edgenode *link; //指向第一条依附该顶点的弧的指针 }vexnode;

void CreateGraphic(vexnode* G,int prnum,int actnum) //创建图 { int begin,end,duttem; edgenode *p; for(int i=0;i<prnum;i++) { G[i].projectname=i; G[i].id=0; G[i].link=NULL; } printf("某项目的开始到结束在图中的结点输入<vi,vj,dut>\n"); printf("如：3,4,9 回车表示第三节点到第四结点之间的活动用了9个单位时间\n"); for(int k=0;k<actnum;k++) { scanf("%d,%d,%d",&begin,&end,&duttem); p=(edgenode*)malloc(sizeof(edgenode)); p->adjvex=end-1; p->dut=duttem; G[end-1].id++; p->next=G[begin-1].link ; G[begin-1].link=p; } }

用带权有向图构造的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;

用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期……

} totaltime=ve[prnum-1]; for(i=0;i<prnum;i++) vl[i]=totaltime; for(i=prnum-2;i>=0;i--) { j=topologystack[i]; p=G[j].link ; while(p) { k=p->adjvex ; if((vl[k]-p->dut)<vl[j]) vl[j]=vl[k]-p->dut ; p=p->next ; } } i=0; printf("| 起点 | 终点 | 最早发生时间 | 最晚发生时间 for(j=0;j<prnum;j++) { p=G[j].link; while(p) { k=p->adjvex ; e[++i]=ve[j]; l[i]=vl[k]-p->dut; printf("| %4d | %4d | %4d | |",G[j].projectname +1,G[k].projectname +1,e[i],l[i],l[i]-e[i]);

if(l[i]==e[i])

printf(" 关键活动 |"); printf("\n"); p=p->next ; } }

return 0; }

void mintime () //计算整个工程所用的最短时间 {

int pn,an,totaltime=0; system("cls");

printf("请输入这个工程的化成图形的结点数:"); scanf("%d",&pn);

printf("请输入这个工程的活动数:");

| 差值 | %4d 备注 |\n"); | %4d

用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期……

scanf("%d",&an);

vexnode* Graphicmap=(vexnode*)malloc(pn*sizeof(vexnode)); CreateGraphic(Graphicmap,pn,an);

SearchMapPath(Graphicmap,pn,an,totaltime);

printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime); system("pause"); }

int main() {

char ch; for(;;) { do { system("cls"); printf("| 欢迎进入求关键路径算法程序 …… 此处隐藏：3061字，全部文档内容请下载后查看。喜欢就下载吧 ……