| 并行最短路径搜索算法的设计与实现 |
| |
| 引用本文： | 卢照,师军. 并行最短路径搜索算法的设计与实现[J]. 计算机工程与应用, 2010, 46(3): 69-71. DOI: 10.3778/j.issn.1002-8331.2010.03.021 |
| |
| 作者姓名： | 卢照 师军 |
| |
| 作者单位： | 陕西师范大学 计算机科学学院，西安 710062 |
| |
| 摘 要： | 针对串行最短路径搜索算法本身固有的局限性，难以随着网络规模的增大而提高搜索速度的问题，设计并实现了一种基于并行Dijkstra思想的并行最短路径搜索算法，使算法复杂度由O（N2）减少到O（N2/p+N*（p-1）），提高了算法的效率。实验结果表明，该算法搜索速度快且性能稳定，当结点数目相当庞大时，算法的优越性更加明显。
|
| 关 键 词： | 最短路径 并行机环境 MessagePassingInterface（MPI） 并行搜索算法 |
| 收稿时间： | 2008-10-30 |
| 修稿时间： | 2009-1-4 |
Design and implementation of parallel shortest path search algorithm |
| |
| LU Zhao,SHI Jun. Design and implementation of parallel shortest path search algorithm[J]. Computer Engineering and Applications, 2010, 46(3): 69-71. DOI: 10.3778/j.issn.1002-8331.2010.03.021 |
| |
| Authors: | LU Zhao SHI Jun |
| |
| Affiliation: | College of Computer Science，Shaanxi Normal University，Xi’an 710062，China |
| |
| Abstract: | In view of the serial search for the shortest path algorithm inherent limitations and the difficult to raising the issue of search speed as the size of the network increases,the parallel shortest path search algorithm is designed and implemented based on the parallel Dijkstra's algorithm idea.The complexity of the algorithm reduces to O(N2/p+N*(p-1)) as compared with the complexity O(N2) of serial Dijkstra's algorithm.Experimental results show that the parallel shortest path search algorithm has fast and st... |
| |
| Keywords: | Message Passing Interface(MPI) the shortest path parallel computer environment Message Passing Intefface(MPI) parallel search algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
