A modified pulse coupled neural network for shortest-path problem

Shortest-path problem is well-known optimization problem and has been studied by many authors in recent years. Typically it is solved by using the famous Dijkstra's algorithm, which would quickly provide a global optimization solution in most instances. However, as the problem scale increases, this method is inefficient and may consume a considerable amount of CPU time. Neural networks, which are massively parallel models, can solve this question easily. This paper presents a novel biological neural network based algorithm for the finding of the shortest path in large scale systems. The start neuron fires first, and then the firing event spreads out through the lateral connections among the neurons, like the propagation of a wave. Then the generated spiking wave spreads at a constant speed so that the time of travel between two neurons is proportional to the path length between them. The computational complexity of the algorithm is only related to the length of the shortest path, and independent of the number of existing paths in the graph. Simulation results show that the proposed method is more efficient than Dijkstra's in the larger scale systems.