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

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

河 南 工 程 学 院

实 习 报 告

系（部） 专 业 班 级 姓 名 学 号

2011 年 7月 1日

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

实 习 （训） 报 告 评 语

等 级：

评阅人： 职称：

年 月 日

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

河南工程学院

实习（训）报告

实习内容： 关键路径问题

实习时间：自 6 月 27 日 至 7 月 1 日 共 5 天

实习地点： 实习单位：

指导教师： 系主任：

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

目 录

一、设计目标 ................................................................................................................................... 1 二、课题分析与设计 ....................................................................................................................... 2

1．课题需求分析 ..................................................................................................................... 2 2．存储结构设计 ..................................................................................................................... 2 3．算法设计 ............................................................................................................................. 3 4．程序流程图 ......................................................................................................................... 4 三、程序清单 ................................................................................................................................... 5 四、测试 ........................................................................................................................................... 9

1．测试数据 ............................................................................................................................. 9 2．测试结果及分析 ................................................................................................................. 9 五、总结 ......................................................................................................................................... 11

1．收获 ................................................................................................................................... 11 2．不足 ................................................................................................................................... 11 3．算法改进分析 ................................................................................................................... 11

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

一、设计目标

用带权有向图构造的AOE网表示一项工程计划，图的结点表示事件，弧表示活动，权值表示活动持续时间。

完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。

求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。

本次实训设计程序，任意给出表示工程计划的顶点及带权弧的有向图信息，即可判断整项工程计划是否合理，求出工程计划中的关键路径及关键活动。完成整项工程至少需要的时间。

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

二、课题分析与设计

1．课题需求分析

1.1问题描述：

（1）选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。

（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。

具体要解决的问题有如下四个：

1） 将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列；

2） 用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图；

3 …… 此处隐藏：3060字，全部文档内容请下载后查看。喜欢就下载吧 ……