[1]张清华,李鸿,沈文..基于点割集的并行最短路径算法[J].郑州大学学报(工学版),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
- 作者:
-
张清华; 李鸿; 沈文.
-
重庆邮电大学计算机科学与技术研究所,重庆400065;重庆邮电大学数理学院,重庆400065, 重庆邮电大学计算机科学与技术研究所,重庆,400065
- 关键词:
-
割点; 最短路径算法; Dijkstra算法; 并行计算; 粒计算
- DOI:
-
10.3969/j.issn.1671-6833.2012.05.028
- 摘要:
-
在研究和分析了Dijkstra算法的基础上,在Dijkstra算法中通过引入点割集和割点的思想来改进Dijkstra算法,该方法首先利用点割集或割点把原问题分解成多个子图,然后对每个子图并行求最短路径,最后通过点割集或割点求出整个原问题的最短路径,从而降低算法的时间复杂度,提高算法的效率.
更新日期/Last Update:
1900-01-01