并行最短路径搜索算法的设计与实现

被引：20

作者：

卢照

师军

机构：

[1] 陕西师范大学计算机科学学院

来源：

计算机工程与应用 | 2010年 / 46卷 / 03期

关键词：

最短路径; 并行机环境; Message Passing Interface(MPI); 并行搜索算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

针对串行最短路径搜索算法本身固有的局限性,难以随着网络规模的增大而提高搜索速度的问题,设计并实现了一种基于并行Dijkstra思想的并行最短路径搜索算法,使算法复杂度由O(N2)减少到O(N2/p+N*(p-1)),提高了算法的效率。实验结果表明,该算法搜索速度快且性能稳定,当结点数目相当庞大时,算法的优越性更加明显。

引用

页码：69 / 71

页数：3

共 11 条

[1]

交通网络分析中的最短路径并行算法研究与实现.[D].倪安宁.吉林大学.2004, 04

[2]

Temination detection for parallel shortst path algorithms..Hribar M R;Taylor V E;.Technical Report CSE-97-004 Computer Science-Engineering;EECS Department;Northwestern University;Chicago.1997,

[3]

并行算法实践.[M].陈国良等编著;.高等教育出版社.2004,

[4]

并行计算.[M].陈国良编著;.高等教育出版社.2003,

[5]

数据结构.[M].严蔚敏;吴伟民编著;.清华大学出版社.2002,

[6]

高性能计算并行编程技术.[M].都志辉编著;.清华大学出版社.2001,

[7] 基于MPICH的MPI并行环境分析 [J].