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

详细信息    查看全文

• 作者：Yudong Zhang ; ^a ; ^{zhangyudongnuaa@gmail.com"" rel=""nofollow} ; Lenan Wu^a ; Geng Wei^a ; Shuihua Wang^a [Author vitae]
• 关键词：All pairs shortest path ; Pulse coupled neural network ; Matrix multiplication ; Parallel algorithm
• 刊名：Digital Signal Processing
• 出版年：2011
• 出版时间：July 2011
• 年：2011
• 卷：21
• 期：4
• 页码：517-521
• 全文大小：305 K

文摘

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 , where n stands for the number of nodes. It is the fastest parallel algorithm compared to traditional PCNN, MOPCNN, and MPCNN methods.