《图的关键路径及求法探析》6000字（论文）

图的关键路径及求法分析摘要 [1].关键路径在项目时间管理上有很大的应用.关键路径上的活动是影响工程项目的关键，找出了关键路径后就可以抓住项目工期管理中的主要矛盾，知道项目哪些部分是必须按时完成的，哪些部分是有多余的时间，从而确定整个项目的工期.对于关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间.而对于不在关键路径上的各个活动，只要在不影响项目完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的.通过关键活动确定关键路径关键活动是为准时完成项目而必须按时完成的活动，即处于关键路径上的活动.所有项目都是由一系列活动组成，而在这些活动中存在各种链接关系和活动约束.其中有些活动如果延误就会影响整个项目工期.在项目中总存在这样一类直接影响项目工期变化的活动，这些活动就是关键活动.由关键活动确定关键路径需要定义以下描述量：（1）表示事件的最早发生时间；（2）表示事件的最迟发生时间；（3）表示活动的最早开始时间；（4）表示活动的最迟开始时间.事件的最早发生时间和最晚发生时间由于整个工程只有一个开始点和一个结束点，所以在AOE网中只有一个入度为零和出度为零的点，它们分别叫做源点和汇点.假设源点为，从到的最长路径长度叫做事件的最早发生时间，这个时间表示了所有以为尾的弧所表示的活动的最早开始时间.而最迟发生时间就是每个顶点对应的事件最晚需要开始的时间，如果超出此时间就会延误整个工期.求最早发生时间和最迟发生时间需要分两步进行：Step1：如果活动由弧表示，其持续时间记为.从开始向前递推，，，，其中，是所有以第个顶点为头的弧的集合.Step2：从起向后递推，，，其中，S是所有以第个顶点为尾的弧的集合.V1V2VV1V2V3V4V5V6a1=30a2=60a3=45a4=60a5=30a6=15图SEQ图\*ARABIC图SEQ图\*ARABIC1AOE网第一步：求解最早发生时间.事件的最早发生时间为0,即,事件的最早发生时间为30，即.事件的最早发生时间是90，即,事件的最早发生时间分别为、、.第二步：求解最迟发生时间.事件的最迟发生时间是180，事件的最迟发生时间为,事件的最迟发生时间为165，即,事件的最迟发生时间,事件的最迟发生时间为,事件的最迟发生时间为0.活动的最早开始时间和最迟开始时间活动的最早开始时间就是事件的最早发生时间，而事件的最迟开始时间是在不耽误工程进度的条件下，活动在最晚限度下开工的时间，两者之差表示完成活动的时间余量，并把的活动叫做关键活动.求最早发生时间和最迟发生时间需要分两步进行：Step1：设活动用弧表示，其持续时间记为，则有如下关系，，由此可得到的最早开始时间.Step2：由，可得到的最迟开始时间.例2用图1求解活动的最早开始时间和最迟开始时间解第一步：求解最早开始时间活动的最早开始时间等于事件的最早发生时间，即，，，，，.第二步：求解最迟开始时间.活动的最迟开始时间为，活动的最迟开始时间为，活动开始时间为，活动的最迟开始时间为，活动的最迟开始时间为150，活动的最迟开始时间为.例1、2所计算的事件的最早最迟发生时间和活动的最早最迟开始时间总结如下表:表SEQ表\*ARABIC1运算结果顶点活动0000030303030090903012090751659090015015015015001801807516590关键活动的确定关键活动的确定有如下步骤： （1）输入条弧,建立AOE网的存储结构；（2）从源点出发，令，求其他各个顶点的最早发生时间().如果算法中得到的拓扑有序序列中所有顶点个数远远小于网中所有顶点数,则说明网中存在环，不能得到关键路径，故算法终止，否则执行（3）；（3）从汇点出发，令,按逆拓扑有序求其余各顶点的最迟发生时间()；（4）根据各顶点的和值，求每条弧的最早开始时间和最迟开始时间，若某条弧满足条件,则为关键活动.由表1可知关键活动为；确定了关键活动之后，关键路径也就随之确定.故图1所示的AOE网的关键路径为.关键路径求解例题例2求AOE网中的关键路径.图SEQ图\*ARABIC图SEQ图\*ARABIC2一个有11项活动的AOE网V11V21V31V4V5V6V7V8V91a1=6a4=1a2=4a3=5a5=1a6=2a7=9a10=2a8=7a9=4a11=4解第一步：求解事件的最早最迟发生时间和活动的最早最迟开始时间.由图2可知，事件V1到V9的最长路径是(V1,V2,V5,V8,V9)，最长路径长度为18.其他事件和活动具体的最早最迟发生时间以及最早最迟开始时间分别如下表所示：表SEQ表\*ARABIC2运算结果顶点V100V266V346V458V577V6710V71616V81414V91818表SEQ表\*ARABIC3求解结果活动a1000a2022a3033a4660a5462a6583a7770a8770a97103a1016160a1114140第二步：找出关键路径.由表2，表3所示可从计算结果得知，关键活动为和，它们分别构成以下两条关键路径和,如下图所示：VV1V2V5V7V8V9a1a4a7a8a10a11图图SEQ图\*ARABIC3关键路径通过Dijkstra算法确定关键路径Dijkstra算法概述Dijkstra算法是很具有代表性的最短路径算法，应用于求解图中一个顶点到其他顶点的最短路径.它的特性是以图中的一个开始点向图中心搜索，搜索到结束点为止.Dijkstra算法求最短路径的基本思想是：在一个带权有向图G=(V,E)中，有一个被划分为不同两组的顶点集合称为V.其中一组划分为已经得到最短路径的顶点集合S，另一组划分为还未明确最短路径的顶点集合U.初始时先选中一个顶点加入到S中，求出它的最短路径，接着每求得一条最短路径，就把顶点加入到S中，直到S中有了全部的顶点，算法就算结束.在每加入一个顶点的计算过程中，需按照最短路径长度递增的顺序加入顶点集合S的规律，并且保证其中所选的源点到S中各顶点的最短路径长度必须不大于源点到U中任何顶点的最短路径长度.另外，集合S的各顶点的路径距离就是从V到此顶点的最短路径长度，而集合U的各顶点的路径距离就是从V到此顶点的只包括S中的顶点为中间顶点的当前最短路径长度.用Dijkstra算法求关键路径的设计思想作为我们所认识的算法，Dijkstra算法可以求出图的最短路径.假设可以为顶点引入前驱数组，那么就可以回溯出图中所有的最短路径.AOE网中的关键路径是从源点到汇点的最远的路径，所以可以根据将图中所有弧的权值全部取相反数的思想，将关键路径转变为最短路径.可以对图中所有边的权值进行分析之后找出最大值，然后取，最后把弧的权值变为.这样不仅能使关键路径变为最短路径，而且能使所有边的权值为非负值，适用于权值不为负的最短路径求解的Dijkstra算法，最后求出最短路径.用Dijkstra算法求关键路径的算法过程算法过程如下：Step1：将AOE网中所有弧的权值，其中为不小于最大权值的正数;Step2：在更改权值后的图中继续使用Dijkstra算法，求出最短路径，并记录最短路径长度;Step3： 输出所有最短路径，即为关键路径，其长度为,其中为该路径穿程边的条数.Dijkstra算法应用a3=3图SEQ图\*ARABIC4AOEa3=3图SEQ图\*ARABIC4AOE网V1V4V0V3V5V2a1=3a2=2a4=1a5=1a6=2a7=1解第一步：对图中所有的弧做出分析，找出最大权值5，取为不小于5的权值，把所有弧的权值重新置为.a3=2a3=2V1V4V0V3V5V2a1=2a2=3a4=4a5=4a6=3a7=4图图SEQ图\*ARABIC5重置后的AOE网第二步：执行Dijkstra算法.取为起始点，与相邻的两个点分别为，它们到的距离分别为2和3，其余为.搜索到的最短路径用集合来表示.此时.因为到的距离最短，所以此时更新，.接着我们看与连接的点，分别有和,它们到的距离分别为4和6，其余的为.此时图中各点到的距离为.因为到的距离最短，所以此时更新，.接着我们看与连接的点，只有，它到的距离为7，比原来的值大，所以不更新.此时图中各点到的距离为.因为到的距离最短，所以此时更新，.接着我们看与相连的点只有，它到的最短距离为8.所以此时图中各点到的最短的距离为.现在只有没有加入到中，它与相连，此时到的最短距离为9，比原来的值大，故不更新.此时，所有的顶点都已经遍历结束.所有的计算结果总结如下表：表SEQ表\*ARABIC4计算结果总结顶点从顶点到各顶点的最短路径前驱结点233666--4488第三步：找出关键路径由第二步可以看出，从起始点到结束点的最短路径长度为8，通过回溯前驱结点，得到关键路径.用两种算法求关键路径及其对比分析用关键活动求关键路径V0V1V0V1V2V3V4V5V6V7V8a2=3a3=5a1=7a4=3a5=8a6=3a7=9a8=10a9=2a10=4a11=3图SEQ图\*ARABIC6AOE网解第一步：求事件的最早发生时间和最迟发生时间事件的最早发生时间为0，事件的最早发生时间，事件的最早发生时间，事件的最早发生时间为，事件的最早发生时间为，事件的最早发生时间为，事件的最早发生时间为，事件的最早发生时间为，事件的最早发生时间为.事件的最迟发生时间是24，事件的最迟发生时间为，事件的最迟发生时间为事件的最迟发生时间为，事件的最迟发生时间为，事件的最迟发生时间为，事件的最迟发生时间为，事件的最迟发生时间为，事件的最迟发生时间为.第二步：求活动的最早开始时间和最迟开始时间活动的最早开始时间都为0，活动的最早开始时间为，活动的最早开始时间为，活动的最早开始时间为，活动的最早开始时间为，活动的最早开始时间为，活动的最早开始时间为，活动的最早开始时间为.活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为，活动的最迟开始时间为.第三步：找出关键活动活动的最早开始时间与最迟开始时间的计算结果总结如下表：表SEQ表\*ARABIC5计算结果活动01100001111781330516111111011110819112020021210第四步：确定关键路径由表4可知，关键活动为，故关键路径一共有两条，即为和.用Dijkstra算法求关键路径例6用Dijkstra算法求例5的关键路径.解第一步：对图中所有的弧做出分析，找出最大权值10，取为不小于10的权值，把所有弧的权值重新置为.比如的权值被置为.所有弧的权值重置后得到的图如下图7所示:图图SEQ图\*ARABIC7权值重置后的AOE网V0V1V2VV0V1V2V3V4V6V7V8V5a1=3a2=7a3=5a4=7a5=2a6=7a7=1a8=0a9=8a10=6a11=7取为起始点，再依次取顶点，加入到中(是已计算出最短路径的顶点集合),得到的结果如下表所示： 表SEQ表\*ARABIC6Dijkstra算法过程 顶点从顶点到各顶点的最短路径前驱结点377755101091212121212--10109161616SVV0V2V4V6V7V8第三步：由上表的运算结果可以看出，从起始点到结束点的最短路径长度为16，为每个顶点引入前驱结点，通过回溯前驱结点得到两条关键路径，V0V2V4V6V7V8图SEQ图\*ARABIC8两条关键路径图SEQ图\*ARABIC8两条关键路径用关键活动确定关键路径的优缺点：用关键活动求关键路径算法优点是它是基于拓扑排序进行的，这种算法的时间复杂度为,是比较好的；但缺点是算法中不仅要使用拓扑排序，还要使用逆拓扑排序，并且还要计算事件的最早最迟发生时间和活动的最早最迟开始时间，所以对于关键路径的求解比较麻烦.用Dijkstra算法来求关键路径的优缺点：根据把关键路径转化为最短路径的思想，提出基于Dijkstra算法求AOE网的关键路径，它的缺点是这种算法的时间复杂度虽然为，但是该算法简单，计算过程相对简单，并且对其存储方式没有要求，可以输出所有关键路径，容易理解，有较强的实用性.

结束语文中主要叙述了求解关键路径的两种算法和时间复杂度分析.总体来说，使用迪杰斯特拉算法求关键路径比较简单实用，更容易输出关键路径.关键路径具有很大的实用性，体现在它能为工程项目提供可视化的图形表示，直观的展现在人们面前，并且通过跟踪关键路径可以平衡工程项目的进度，及时的找出项目进程中的漏洞，判断是否有必要采取行动来完成工程的预计目的，节约成本.但是也有一些不足之处，比如在应用的过程中，由于工程项目的模式在不断地更新，所以关键路径的应用也需要不断地探索与改进.

参考文献严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社，2004:183-186.李青.数据结构中关键路径算法的原理及实现[J].计算机产品与流通，2019（06）:113.李春葆等.数据结构与算法教程[M].北京：清华大学出版社，2007:1