《关键路径》实验报告.pdf

《数据结构与算法（实验）》实验报告

学院：管理科学与工程系别：计算机科学与技术

实验地点时间2012-3-19

关键路径东校实验

题目

楼2-204

班级学号姓名

对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该

图的关键路径的程序。设一个工程有n项活动，e个事件。其中：活动1——表示

整个工程开始；活动n——表示整个工程结束.

问

问题：完成整项工程至少需要多少时间？哪些活动是影响工程进度的关键？

题

描

述

数Ve(j)——表示事件Vj的最早发生时间

据Vl(j)——表示事件Vj的最迟发生时间

模e(i)——表示活动ai的最早开始时间

型l(i)——表示活动ai的最迟开始时间

与l(i)-e(i)——表示完成活动ai的时间余量

需关键活动——关键路径上的活动，即l(i)=e(i)的活动

求设活动ai用弧j,k表示，其持续时间记为dut(j,k)。则有

e(i)=Ve(j)

描l(i)=Vl(k)-dut(j,k)

如何求Ve(j)和Vl(j)？

述

从Ve(1)=0开始向前递推

Ve(j)Max{Ve(i)dut(i,j)},i,jT,2jn

i

中中T中中中中j中中中中中中中

从Vl(n)=Ve(n)开始向后递推

Vl(i)Min{Vl(j)dut(i,j)},i,jS,1in1

j

中中S中中中中中i中中中中中中

程序功能：根据输入的图的信息，能够建立AOE-网，并能够输出关键路径所

在的边。

主函数main()

概

建图函数CreateGraph()

要

求解关键路径函数CriticalPath()

设

计

intCriticalpath(ALGraphG){

/*G为有向网，输出G的各项关键活动。*/

InitStack(T);/*建立用于生拓扑逆序的栈T*/

if(!TopologicalOrder(G,T))

return0；/*该有向网有回路返回0*/

vl[0..G.vexnum-1]=ve[G.vexnum-1];/*初始化顶点事件的最迟发生时间

*/

while(!StackEmpty(T))/*按拓扑逆序求各顶点的vl值*/

详for(Pop(T,j),p=G.adjlist[j].firstedge;p;p=p-next){

k=p-adjvex;

dut=*(p-info);

细

if(vl[k]-dutvl[j])vl[j]=vl[k]–du