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

发布时间：2018-05-12 19:34

本文选题：关键路径 + PERT/CPM图　；参考：《中国科技论文》2017年17期

【摘要】：为了研究简单图的有关路径问题,将简单有向赋权图对应的邻接矩阵推广到二维元素的初始邻接路径矩阵和一般邻接路径矩阵,定义了一般邻接路径矩阵的"乘法"运算,通过其"乘法"运算可以同时求出简单有向无环赋权图中任意2点间的最大权值以及对应的路径,从而可以同时求出计划评审方法(program evaluation and review technique,PERT)图与关键路线方法(critical path method,CPM)图中的关键路径与对应的最大权值,本方法的优点是所求路径与对应权值同时显示在最终的一般邻接路径矩阵上。本算法易于通过计算机编程实现,对于大规模PERT/CPM图或简单有向无环赋权图,更有优势。
[Abstract]:In order to study the path problem of simple graph, the adjacent matrix corresponding to simple directed weighted graph is extended to the initial adjacent path matrix of two-dimensional elements and the general adjacent path matrix, and the "multiplication" operation of the general adjacent path matrix is defined. By means of its multiplication operation, the maximum weight value and the corresponding path between any two points in a simple directed acyclic weighted graph can be obtained at the same time. Therefore, the critical path and the corresponding maximum weights in the program evaluation and review technique / pert diagram and the critical route method / critical path method chart can be obtained at the same time. The advantage of this method is that the calculated path and the corresponding weights are displayed simultaneously on the final general adjacent path matrix. This algorithm is easy to realize by computer programming, and has more advantages for large-scale PERT/CPM diagrams or simple directed acyclic weighted graphs.
【作者单位】：武汉轻工大学数学与计算机学院;
【基金】：国家自然科学基金资助项目(61179032,11301405)
【分类号】：O157.5

【相似文献】