Computing k shortest paths using modified pulse-coupled neural network

The K Shortest Paths (KSPs) problem with non-numerable applications has been researched widely, which aims to compute KSPs between two nodes in a non-decreasing order. However, less effort has been devoted to single-source KSP problem than to single-pair KSP computation, especially by using parallel methods. This paper proposes a Modified Continued Pulse Coupled Neural Network (MCPCNN) model to solve the two kinds of KSP problems. Theoretical analysis of MCPCNN and two algorithms for KSPs computation are presented. By using the parallel pulse transmission characteristic of pulse coupled neural networks, the method is able to find k shortest paths quickly. The computational complexity is only related to the length of the longest shortest path. Simulative results for route planning show that the proposed MCPCNN method for KSPs computation outperforms many other current efficient algorithms.