Closed semiring connectionist network for the Bellman-Ford computation

The Bellman-Ford algorithm (R. Bellman, 1958; L.R. Ford, 1956) is well known for providing a dynamic programming solution for the shortest path problem. Alternatively, the closed semiring is an algebraic structure which unifies a family of path problems, including all pairs shortest path, transitive closure and minimum spanning tree, defined on directed or undirected graphs. The paper proposes a connectionist network architecture, called the binary relation inference network, which incorporates the Bellman-Ford computation for solving closed semiring problems. The extension and summary operators of closed semirings correspond to the site and unit functions of the network. The inference network structure offers an obvious advantage of being simply extensible for asynchronous and continuous time operation. Implementation in analogue processing circuits promises a practical problem size independence in the solution time. VLSI circuits are also presented and limiting factors of performance are discussed, with particular reference to the minimum spanning tree problem