|
|||||
|
|
| 基于简化DPCNN的最短路径算法 | |
| 引用本文： | 张煜东,吴乐南,王水花,段力,Neggaz Nabil.基于简化DPCNN的最短路径算法[J].交通与计算机,2010,28(1):6-9. |
| 作者姓名： | 张煜东 吴乐南 王水花 段力 Neggaz Nabil |
| 作者单位： | 1. 东南大学信息科学与工程学院,南京,210096 2. 东南大学交通学院,南京,210096 3. 奥兰科技大学计算机科学学院,奥兰,阿尔及利亚 |
| 基金项目： | 国家自然科学基金项目，国家高技术研究发展计划项目，高等学校科技创新工程重大培育资金项目，江苏省自然科学基金项目，东南大学优秀博士学位论文基金项目 |
| 摘 要： | 传统求解最短路径（SP）问题的方法一般有组合技术与代数方法2大类，但算法复杂度的指数上界为2．376，不能实时对大规模SP问题进行求解。文中提出1种简化的时延脉冲耦合神经网络（SDPCNN）模型，可1次求解源点到其他所有点的最短路径，算法时间复杂度仅有O（n）．实验证实了这一模型的有效性，且计算时间仅为未简化模型的5％～10％。 |
| 关 键 词： | 时延脉冲耦合神经网络 最短路径 并行算法 |
Solution for All Pairs Shortest Path Problem via Simplified DPCNN |
|
| ZHANG Yudong,WU Lena,WANG Shuihua,DUAN Li,Neggaz Nabil.Solution for All Pairs Shortest Path Problem via Simplified DPCNN[J].Computer and Communications,2010,28(1):6-9. | |
| Authors: | ZHANG Yudong WU Lena WANG Shuihua DUAN Li Neggaz Nabil |
| Institution: | ZHANG Yudong WU Lenan WANG Shuihua DUAN Li Neggaz Nabii(School of Information Science and Engineering, Southeast University, Nanjing 210096, China)1(Transportation College, Southeast University, Nanjing 2]0096, China )2(College of Computer Science, University of Science and Technology of Oran, Oran, Algeria)3 |
| Abstract: | 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. |
| Keywords: | delay pulse coupled neural network shortest path parallel algorithm |
| 本文献已被 维普 万方数据 等数据库收录！ | |