基于最短路算法的关键路线求法

韦利春 高红慧 王艳娟 王慧 高红彬

摘要：计划评审方法（PERT）和关键路线法（CPM）是网络分析的重要组成部分，它广泛地用于系统分析和项目管理。文章基于图的邻接矩阵，利用最短路算法，求得关键路线。该关键路线的算法容易理解、掌握，并便于使用Matlab实现。

关键词：邻接矩阵；Floyd算法；关键路线；Matlab

中图分类号：TM744 文献标识码：A 文章编号：1009-2374（2012）06-0046-02

一、概述

计划评审方法（PERT）和关键路线法（CPM）是网络分析的重要组成部分，它广泛地用于系统分析和项目管理。计划评审与关键路线方法是在20世纪50年代提出并发展起来的，1956年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法。1958年，美国海军武装部在研制“北极星”导弹计划时，由于导弹的研制系统过于庞大、复杂，为找到一种有效的管理方法，设计了计划评审方法。由于PERT与CPM既有着相同的目标应用，又有很多相同的术语，这两种方法已合并为一种方法，在国外称为PERT/CPM，在国内称为统筹方法（Scheduling Method）。

通常的关键路线法较复杂，较难上机实现。本文提出一种基于最短路算法的关键路线求法，该方法易理解掌握，并易于使用图的邻接矩阵上机实现。

二、算法设计

如果把关键路径看成是网络中从起点到终点的最长路，并且把网络看成是一个有向图，其中是顶点集合，是弧的集合，为邻接矩阵，这里，，，为弧的权重。我们就可以利用图的最短路算法，以求得关键路线。

为了把最长路径问题转化为最短路径问题，首先把有向图转化为另一个有向图，其中满足

，，。

这样我们就可以把中求最长路径的问题，转化为中求最短路的算法。求最短路的算法有很多，例如有广度优先搜索算法、宽度优先搜索算法、Dijkstra标号算法和Floyd算法等。由于广度优先搜索算法和宽度优先搜索算法较难实现，Dijkstra标号算法不适用于负权的图，这样最佳算法就是使用Floyd算法求中的最短路径。

Floyd算法是求图中所有顶点对之间最短路径的算法。Floyd算法具体如下，对于赋权图，记。

Floyd算法是递推产生一个矩阵序列，其中矩阵的第行第列元素表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。

计算时用迭代公式，是迭代次数，。

最后，当时，即是各顶点之间的最短通路值。

三、计算实例

某项目工程由11项作业组成（分别用代号表示），其计划完成时间及作业间相互关系如表1所示，求作业的关键路径。

图1中的计划网络图就是一个有向图，其中顶点集合，为弧的集合，邻接矩阵。

关键路径实际上是求从到的最长路径，为了把最长路径问题转化为最短路径问题，为此我们构造赋权有向图，邻接矩阵，

其中：

。

这样我们只要求得赋权有向图从到的最短路径，就等价地得到有向图中的关键路径。

利用最短路的Floyd算法，使用Matlab软件，可以求得关键路径为1→3→5→6→8，关键路径的长度为51。

四、结论

本文提出了利用有向图邻接矩阵的最短路算法，来计算网络的关键路径，把最短路算法和关键路径算法有机地结合起来，该算法的思路十分自然，容易理解，并且便于用Matlab软件实现。

参考文献

[1]司守奎，孙玺菁．数学建模算法与应用[M]．北京：国防工业出版社，2011．

[2]谢金星，薛毅．优化建模与LINDO/LINGO软件[M]．北京：清华大学出版社，2005．

作者简介：韦利春（1985-），男，山东德州人，烟台南山学院高级技师，研究方向：实训教学；高红慧（1985-），女，吉林白城人，烟台南山学院助教，研究方向：自动化控制；王艳娟（1981-），女，吉林白城人，烟台南山学院助教，研究方向：实训教学；王慧（1986-），女，山东临沂人，烟台南山学院教师，硕士，研究方向：实训教学；高红彬（1988-），男，山东高密人，供职于诚海电子有限公司，研究方向：电子技术。

（责任编辑：周加转）