A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network

摘要

All pairs shortest path (APSP) is a classical problem with diverse applications. Traditional algorithms are not suitable for real time applications, so it is necessary to investigate parallel algorithms. This paper presents an improved matrix multiplication method to solve the APSO problem. Afterwards, the pulse coupled neural network (PCNN) is employed to realize the parallel computation. The time complexity of our strategy is only O(log~2 n), where n stands for the number of nodes. It is the fastest parallel algorithm compared to traditional PCNN, MOPCNN, and MPCNN methods.