图的邻接路径矩阵与关键路径求解算法

• 作者: 杨波 程果 高遵海
• 来源期刊: 中国科技论文
• 学科: 工学
• 关键词: 关键路径 PERT/CPM图 简单有向无环赋权图 邻接路径矩阵 邻接路径矩阵乘法
• 年，卷（期）: 2017,（17）
• 页码范围: 2003-2007
• 页数: 5页
• 分类号: O157.5|TP301.6
• 字数: 4531字
• 语种: 中文

摘要

为了研究简单图的有关路径问题,将简单有向赋权图对应的邻接矩阵推广到二维元素的初始邻接路径矩阵和一般邻接路径矩阵,定义了一般邻接路径矩阵的"乘法"运算,通过其"乘法"运算可以同时求出简单有向无环赋权图中任意2点间的最大权值以及对应的路径,从而可以同时求出计划评审方法(program evaluation and review technique,PERT)图与关键路线方法(critical path method,CPM)图中的关键路径与对应的最大权值,本方法的优点是所求路径与对应权值同时显示在最终的一般邻接路径矩阵上.本算法易于通过计算机编程实现,对于大规模PERT/CPM图或简单有向无环赋权图,更有优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高遵海	武汉轻工大学数学与计算机学院	5	7	2.0	2.0
2	杨波	武汉轻工大学数学与计算机学院	3	4	1.0	2.0
3	程果	武汉轻工大学数学与计算机学院	3	7	2.0	2.0