| 毕业设计 求关键路径的一个算法 共26页，6350字 附任务书 摘 要 在AOE-网中有些活动可以并行的进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度。而长度最长的路径叫做关键路径。 本文对图论中有关关键路径的概念进行阐述；并通过对传统的求关键路径的算法进行总结，提出了另一种求关键路径的算法，其基本思想是：当从源点到某一点的最大路径改变时，那么从源点到该点的邻接点的最大路径也将发生改变。 本文对该算法的复杂度进行了粗略的分析；并且，为了验证该算法的可行性，本论文还给出了该算法的实现程序。 关键词 关键路径；有向无环图；AOE-网；赋权图 目 录 1 引 论•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••1 2 图的基本概念•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••1 3.传统的关键路径的求法••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••5 4 该算法的基本思想•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••7 5 具体步骤•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••7 6 例 子•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••8 7 算法分析•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••11 8.结束语••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••12 参考文献••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••13 |
查看评论
已有0位网友发表了看法