关键路径求解

《关键路径求解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构中关键路径算法的实现与应用摘 要 介绍求关键路经的算法，对于给出的事件结点网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。关键词 关键路径最少时间1：引言通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”的子工程，这个工程就可以完成了。通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动Vi必须先于活动Vj进行。如果在无有向环的带权有向

2、图中用有向边表示一个工程中的各项活动（ACTIVITY），用有向边上的权值表示活动的持续时间（DURATION），用顶点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称AOE（activeonedges）网络。   AOE网络在某些工程估算方面非常有用。他可以使人们了解：        （1）：研究某个工程至少需要多少时间？        （2）：那些活动是影响工程进度的关键？在AOE网络中，有些活动可以并行的进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然

3、不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（criticalpath）。2：设计步骤：　　　　1:以某一工程为蓝本，采用图的结构表示实际的工程计划的时间。　　　　2:调查以分析和预测这个工程计划个阶段的时间。　　　       3:用调查的结果建立ＡＯE网（ActivityOnEdgeNetwork），即边表示活动的网络，并用图的形式表示。4:用图来存储这些信息。       5:用CreateGraphic

4、();函数建立AOE图。       6:用SearchMapPath();函数求出最大路径，并打印出关键路径。       7:编写代码       8:测试3:设计代码：#include#include#include#include//#definePROJECTNUMBER 9//10//#definePLANNUMBER11//13typedefstructnode{      intadjvex;      intdut;      structnode*

5、next;}edgenode;typedefstruct{      int projectname;      int id;      edgenode*link;}vexnode;//vexnodeGraphicmap[PROJECTNUMBER];voidCreateGraphic(vexnode*Graphicmap,intprojectnumber,intactivenumber){      intbegin,end,duttem;      edgenode*p;      for(inti=0;i

6、+)      {       Graphicmap[i].projectname=i;            Graphicmap[i].id=0;            Graphicmap[i].link=NULL;      }          printf("某项目的开始到结束在图中的节点输入");      printf("如：3,4,9回车表示第三节点到第四节点之间的活动用了9个单位时间");      for(intk=0;k

7、canf("%d,%d,%d",&begin,&end,&duttem);            p=(edgenode*)malloc(sizeof(edgenode));            p->adjvex=end-1;             p->dut=duttem;            Graphicmap[end-1].id++;            p->next=Graphicmap[begin-1].link;            Graphicmap[begin-1].link=p;      }}intSearc

8、hMapPath(vexnode*Graphicmap,intprojectnumber,intactivenumber,