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

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

对于带权有向图构造的AOE网，采用链式存储结构，定义的结构体如下： typedef struct node //定义表结点 {

int adjvex; //该弧所指向的顶点的位置 int dut; //弧的权值

struct node *next; //指向下一条弧的指针 }edgenode;

typedef struct //定义头结点 {

int projectname; //顶点信息 int id; //结点入度

edgenode *link; //指向第一条依附该顶点的弧的指针 }vexnode; 3．算法设计

3.1 算法准备

为求关键路径，设开始点是V1，从V1到Vi的最长路径长度叫做事件Vi的最早发生时间。这个时间决定了所有以Vi为尾的弧所表示的活动的最迟开始时间。用e(i)表示活动ai的最早开始时间。用l(i)表示活动的最迟开始时间，即在不推迟整个工程完成的前提下，活动ai最迟必须开始的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。其中l(i)=e(i)的活动叫做关键活动。用ve(i) 表示事件开始的最早时间，vl(i)表示事件开始的最晚时间。

设活动ai由弧<j,k>(即从顶点j到k)表示，其持续时间记为dut(<j,k>),则：

e(i)=ve(j) l(i)=vl(k)-dut(<j,k>)

求ve(i)和vl(j)分两步： （1）.从ve(1)=0开始向前递推

ve(j)=Max{ ve(i)+dut(<i,j>) }

<i,j>T, 2<=j<=n

其中，T是所有以j为弧头的弧的集合。 （2）.从vl(n)=ve(n)开始向后递推

vl(i)=Min{ vl(j)-dut(<i,j>) }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构求关键路径实习报告(7)在线全文阅读。