Systolic mapping of inference network for the all-pair shortest path problem

The structure, algorithm, and implementation of a binary relation inference network for the all-pair N-node shortest path problem are introduced. The network consists of N² simple computational elements, where each element communicates with 2(N-1) other elements. The algorithm can be executed both synchronously and asynchronously, and can also be extended to the continuous time domain. It converges to the global minimum state within log₂(N-1) synchronous iterations. The algorithm can be mapped on a N×N systolic processor array, in which each processor communicates only with its four neighbors, and the completion time is no longer than Nlog₂(N-1) units of time. On the Connection Machine, it outperforms the algorithm of Y. Robert and D. Trystram (1986), which has a predicted completion time of 5N-2 time units