最小路集的邻接终点矩阵算法  

Algorithm for Obtaining Minimal Path-Set from Adjacency Matrix and Terminal Matrix

作　　者：袁亚华[1] 王自果[1] 

机构地区：[1]西北工业大学

出　　处：《西北工业大学学报》1989年第4期473-478,共6页Journal of Northwestern Polytechnical University

摘　　要：本文定义了邻接矩阵与终点矩阵间的一种特殊运算,直接求得网络的最小路集。本算法具有步骤明确、规则简单,概念清楚、易于应用的特点。本算法只需进行判断和赋值,与现有算法[1,2]相比,避免了乘加等复杂运算,因此还具有运算速度快的特点。文中给出了算法的收敛性证明,以及算法的步骤和框图,并举例对算法进行了说明。It is well known that the minimal path-set has been applied extensively to system reliability analysis, graph theory, electric network and system engineering. Many works have been devoted to the problem of finding the minimal path-set [3,4,5]. But, The adjacency method [3] and the terminal method [4] need a series of operations of multiplication and addition, so the speed of computation has been adversely affected. In this paper, a new algorithm is developed for finding the minimal pathset. From the known adjacency matrix A_1 and known terminal matrix R, A_2 can be obtained by a special operation '*'. A_2=A_1*R, in general A_r=A_(r-1)*R (r=1,2,3,…). With A_1, A_2,…, A_(n-1) known, the minimal path-set can be found. This algorithm needs judgment only, avoiding multiplication, addition, and other operations, so it raises the computational efficiency. The algorithm is illustrated by using a network example with five nodes.

关 键 词：网络 算法 最小路集 

分 类 号：T-55[一般工业技术]