【图的关键路径及求法探究5300字（论文）】

目录摘要 [6];（3） 输出所有最短路径，即为关键路径，其长度为,其中为该路径穿程边的条数.算法应用举例例4以下图6为例，求解源点到汇点的所有关键路径及长度.图SEQ图\*ARABIC6图SEQ图\*ARABIC6一个有12项活动的AOE网V0V1V2V3V4V5V6V7V8a2=3a3=5a1=7a4=3a5=8a6=3a7=9a8=10a9=2a11=4a12=3图SEQ图\*ARABIC7重置后的图V0V1V2V3图SEQ图\*ARABIC7重置后的图V0V1V2V3V4V6V7V8V5a1=3a2=7a3=5a4=7a5=2a6=7a7=1a8=0a9=8a10=6a11=7所有弧的权值重置后得到的图如下图7所示:图SEQ图\*ARABIC8权值重置后的图第二步：对图图SEQ图\*ARABIC8权值重置后的图取为起始点，再依次取顶点，加入到中(是已计算出最短路径的顶点集合),得到的结果如下表所示： 表SEQ表\*ARABIC4Dijkstra算法过程 顶点从顶点到各顶点的最短路径前驱结点377755101091212121212--10109161616SVV0V2V4V6V7V8图8两条关键路径第三步：由上表的运算结果可以看出，从起始点到结束点V0V2V4V6V7V8图8两条关键路径时间复杂度对比通常的关键路径算法时间复杂度分析：像1.2中提到的关键路径算法是基于拓扑排序进行的，这种算法的时间复杂度为,是比较好的；但是算法中不仅要使用拓扑排序，还要使用逆拓扑排序,牵扯到最早最迟发生时间，所以算法本身比较麻烦.利用Dijkstra算法来实现关键路径的算法时间复杂度分析：根据把关键路径转化为最短路径的思想，提出基于Dijkstra算法求AOE网的关键路径，这种算法的时间复杂度虽然为，但是该算法简单，并且对其存储方式没有要求，可以输出所有关键路径，容易理解，有较强的实用性.

结束语文中主要叙述了关键路径的算法思想，求解过程以及应用，并且利用Dijkstra算法求解关键路径.总体来说，关键路径的优点体现在它能为工程项目提供可视化的图形表示，直观的展现在人们面前，并且通过跟踪关键路径可以平衡工程项目的进度，及时的找出项目进程中的漏洞，判断是否有必要采取行动来完成工程的预计目的，节约成本.但是也有一些不足之处，比如在应用的过程中，由于工程项目的模式在不断地更新，所以关键路径的应用也需要不断地探索与改进.

参考文献严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社，2004:183-186.李青.数据结构中关键路径算法的原理及实现[J].计算机产品与流通，2019，（06）:113.李春葆等.数据结构与算法教程[M].北京：清华大学出版社，2007:12.ThomasH.Cormen.算法导论[M].3版.北京：机械工业出版社，2013(12):18.（美）AnanyLevitin.算法设计与分析[M].潘彦，译.北京：清华大学出版社，2015:34.谢科，丁皓明.AOE网中求取关键路径的一种新算法[J].阿坝师范学院学报，2017，34（03）:121-122.刘井莲，赵卫绩.一种改进的关键路径求解算法[J].佳木斯大学学报（自然科学版），2016，34（06）:1008-1010.徐凤生.一种新的关键路径求解算法[J].计算机应用与软件，2005，22(06)：97-99.高遵海，杨波，程果.图的邻接路径矩阵与关键路径求解算法[J].中国科技论文，2017，12（17）:2003-2007.朱志雄.关键路径的矩阵计算公式[J].湖北大学学报(自然科学版)，2014，36(06):542.韦利春，高红慧，王艳娟，王慧，高红彬.基于最短路算法的关键路线求法[J].中国高新技术企业，2012，（06）:46-47.詹泽梅.一种基于动态规划法的关键路径算法[J].电脑知识与技术，2019，15（31）:215-217.林铭德，戴一璟.基于EVM矩阵求解关键路径的方法