郑州大学学报（工学版）2012，Vol.33Issue(5)：125-129,5.DOI:10.3969/j.issn.1671-6833.2012.05.028
基于点割集的并行最短路径算法
Parallel Shortest Path Algorithm Based on Vertex Cut-set
摘要
Abstract
In this paper, research and analysis on the basis of the Dijkstra algorithm, the Dijkstra algorithm by introducing the vertex of cut sets and cut the vertex of idea to improve the Dijkstra algorithm, this method first vertex cut-set or cut vertex to the original problem is decomposed into multiple sub-graph, then the shortest path on each sub-graph parallel to the shortest path of the original problem, and finally obtained by the vertex cut-set or cut vertex, which reduces the time complexity of the algorithm and improves the efficiency of the algorithm.关键词
割点/最短路径算法/Dijkstra算法/并行计算/粒计算Key words
cut vertex/ shortest path algorithm/ Dijkstra algorithm/ parallel computing/ granular computing分类
信息技术与安全科学引用本文复制引用
张清华,李鸿,沈文..基于点割集的并行最短路径算法[J].郑州大学学报（工学版）,2012,33(5):125-129,5.基金项目
重庆市教委科学技术研究项目(KJ110512)和重庆市教委教改项目(No.103161)资助 （KJ110512）
重庆邮电大学研究生教育创新计划资助项目(Y201110). （Y201110）
