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

用带权有向图构造的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．程序流程图

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