基于简化DPCNN的最短路径算法

Solution for All Pairs Shortest Path Problem via Simplified DPCNN

传统求解最短路径（SP）问题的方法一般有组合技术与代数方法2大类，但算法复杂度的指数上界为2．376，不能实时对大规模SP问题进行求解。文中提出1种简化的时延脉冲耦合神经网络（SDPCNN）模型，可1次求解源点到其他所有点的最短路径，算法时间复杂度仅有O（n）．实验证实了这一模型的有效性，且计算时间仅为未简化模型的5％～10％。

Traditional solutions for all pairs shortest path （SP） problem mainly consists of two types： combination method and algebraic method. However, their upper bound on the exponent of 2. 376 is too high for real time large scale shortest path problem. A simplified delay pulse coupled neural network （SDPCNN） was proposed in this paper in order to solve the SP faster, which can obtain SP from specified point to all other points in one computation. Its time complexity is only O（n）. Experiments demonstrate that the simplification is valid and the time consumption via SDPCNN is only 5 %- 10%of that of DPCNN.