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

Adjacent path matrix of graph and critical path algorithm

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

In order to research some path problems of a simple graph,the adjacent matrix corresponding to a simple weighted directed graph is generalized to the initial adjacent path matrix and general adjacent path matrix whose entries are two-dimensional elements.The multiplication operation of the general adjacent path matrices is defined,by which all the maximum weights and their paths of all pairs in simple weighted directed acyclic graph can be found.This method can also be used to find the critical paths and their weights in graph of PERT（program evaluation and review technique）and CPM（critical path method）.The advantage of this method is that the selected paths and their weights are shown clearly at the same time in the final general adjacent path matrix.This algorithm is easy to be realized by computer program.It is more intuitive and will not miss any path for largescale PERT/CPM graph or simple weighted directed acyclic graph.