A neural network for path search in directed graphs

The use of a Boltzmann machine to search for the shortest path in a directed graph (digraph) whose edge weights are equal is discussed. The adjacency matrix of the digraph is employed in the Boltzmann machine topology such that each entry in the adjacency matrix corresponds to a computation node of the Boltzmann machine. The quadratic performance function, for which the Boltzmann machine finds minima, is defined using the syntactic constraints that a path specification has to satisfy. An example application of the proposed method employing a 10-node digraph is demonstrated