[1]张清华,李鸿,沈文..基于点割集的并行最短路径算法[J].郑州大学学报(工学版),2012,33(05):125-129.[doi:10.3969/j.issn.1671-6833.2012.05.028]
　ZHANG Qinghua,LI Hong,SHEN Wen.Parallel Shortest Path Algorithm Based on Vertex Cut-set[J].Journal of Zhengzhou University (Engineering Science),2012,33(05):125-129.[doi:10.3969/j.issn.1671-6833.2012.05.028]
点击复制

基于点割集的并行最短路径算法()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
33
期数:
2012年05期
页码:
125-129
栏目:
出版日期:
2012-09-10

文章信息/Info

Title:
Parallel Shortest Path Algorithm Based on Vertex Cut-set
作者:
张清华; 李鸿; 沈文.
重庆邮电大学计算机科学与技术研究所,重庆400065;重庆邮电大学数理学院,重庆400065, 重庆邮电大学计算机科学与技术研究所,重庆,400065
Author(s):
ZHANG Qinghua; LI Hong; SHEN Wen
1.Institute of Computer Science & Technology, Chongqing University of Posts and Telecommunications, Chongging 400065,China;2. College of Mathematics & Physies, Chongqing University of Posts and Telecommunieations, Chongqing 400065, China
关键词:
割点;  最短路径算法;  Dijkstra算法;  并行计算;  粒计算
Keywords:
cut vertex;  shortest path algorithm;  Dijkstra algorithm;  parallel computing;  granular computing
分类号:
TP301.6
DOI:
10.3969/j.issn.1671-6833.2012.05.028
摘要:
在研究和分析了Dijkstra算法的基础上,在Dijkstra算法中通过引入点割集和割点的思想来改进Dijkstra算法,该方法首先利用点割集或割点把原问题分解成多个子图,然后对每个子图并行求最短路径,最后通过点割集或割点求出整个原问题的最短路径,从而降低算法的时间复杂度,提高算法的效率.
Abstract:
In this paper, research and analysis on the basis of the l)ijkstra algorithm, the Dijkstra algorithm byintroducing the vertex of cut sets and cut the vertex of idea to improve the Dijkstra algorithm, this method firsvertex eut-set or cut vertex to the original problem is decomposed into multiple sub-graph, then the shortes!path on each sub-graph parallel to the shortest path of the original problem , and finally obtained by the vertexcut-set or cut vertex, which reduces the time complexity of the algorithm and improves the efficieney of the al-gorithm.
更新日期/Last Update: 1900-01-01