Patent Document ID: 4748660
Application ID: 06749007
Patent Flag: 1

Claim One:
1. In a network of p nodes interconnected by a number of links, p being a positive whole number, a method for determining the last intermediate node of a pathway from the m-th node to the n-th node through the minimum possible number of nodes, said method being especially useful for communications routing between interconnected computers and between interconnected telephone switchboard systems and comprising the steps of: (a) electronically determining all direct links between nodes of said network; (b) electronically establishing a square matrix R.sub.1 =.parallel.a.sub.ij .parallel..sub.p.sup.p and storing the matrix R.sub.1 in a memory device, a.sub.ij being assigned a value of zero if there is no direct link between the i-th node and the j-th node of the network and being assigned a non-zero value if there is such a direct link, (c) determining whether there is a two-link pathway from the m-th node to the n-th node by electronically comparing elements of equal rank in the m-th row and n-th column of the matrix R.sub.1, the existence of non-zero elements of equal rank indicating the presence of a two-link pathway and the rank of such non-zero elements indicating the location of an intermediate node of that pathway; and (d) in the absence of a two-link pathway, iterating the following steps over all q from 2 to p-2 until a pathway of q+1 links from the m-th node to the n-th node has been determined: (1) electronically establishing elements of the square matrix X.sub.q =.parallel.x.sub.ij .parallel..sub.p.sup.p, which is the product of the matrices R.sub.q-1 and R.sub.1 ; (2) electronically establishing elements of the square matrix R.sub.q =.parallel.b.sub.ij .parallel..sub.p.sup.p, b.sub.ij being assigned a non-zero value if one of x.sub.ij and a.sub.ij is non-zero and being assigned a value of zero if x.sub.ij and a.sub.ij are both zero, and (3) electronically comparing elements of equal rank in the m-th row of matrix R.sub.q and the n-th column of matrix R.sub.1, the existence of non-zero elements of the same rank indicating the presence of said pathway of q+1 links from the m-th node to the n-th node and the rank of such non-zero elements indicating the identity of the last intermediate node of such pathway.