关键路径问题的算法实现和动态演示.doc

摘要：在企业的项目管理中，经常将AOE用来描述项目的进展情况，AOE网中的各顶点表示项目的具体进展情况，边用来表示项目中的各分类任务。AOE网中，项目从始发点到结束点所需时间最短的最长路径被称为关键路径。

在本设计主要是利用三种算法求解出图中的关键路径和动态演示。在设计中分别使用了三种算法来求解关键路径，分别是拓扑排序、深度优先搜索和动态规划。再对这三种算法进行分析比较，得出结论；最后，通过关键路径的动态演示来形象的说明关键路径求解的具体过程。

关键词：AOE网 关键路径 拓扑排序 深度优先搜索 动态规划

目录

摘要

Abstract

1绪论-1

1.1研究背景及意义-1

1.2 论文结构-2

2图及关键路径-3

2.1图的定义和存储表示-3

2.1.1图的定义-3

2.1.2图的存储结构-3

2.2 AOE网及关键路径-5

2.2.1 AOE网-5

2.2.2 关键路径-6

3关键路径的求解算法-7

3.1 拓扑排序算法-7

3.1.2 算法思想-7

3.1.2 算法描述-7

3.1.3 算法实现与分析-8

3.2 广度优先搜索算法-10

3.2.1 算法思想-10

3.2.2 算法描述-10

3.2.3 算法实现与分析-10

3.3动态规划算法-13

3.3.1 算法思想-13

3.3.2 算法描述-14

3.3.3 算法实现与分析-14

4关键路径算法的动态演示-17

4.1平台介绍-17

4.2基本结构-17

4.3动态演示效果-17

5总结与展望-19

致谢-20

参考文献-21