期刊论文

中文

中国科技论文

2095-2783

2017

12

17

2003-2007

10.3969/j.issn.2095-2783.2017.17.015

61179032:国家自然科学基金 11301405:国家自然科学基金

本校为第一机构

为了研究简单图的有关路径问题,将简单有向赋权图对应的邻接矩阵推广到二维元素的初始邻接路径矩阵和一般邻接路径矩阵,定义了一般邻接路径矩阵的"乘法"运算,通过其"乘法"运算可以同时求出简单有向无环赋权图中任意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 ...