基于点割集的并行最短路径算法

• 作者: 张清华 李鸿 沈文
• 来源期刊: 郑州大学学报（工学版）
• 学科: 工学
• 关键词: 割点 最短路径算法 Dijkstra算法 并行计算 粒计算
• 年，卷（期）: 2012,（5）
• 所属期刊栏目: 计算机与电气工程
• 页码范围: 125-129
• 分类号: TP301.6
• 字数: 3881字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-6833.2012.05.028

摘要

在研究和分析了Dijkstra算法的基础上,在Dijkstra算法中通过引入点割集和割点的思想来改进Dijkstra算法,该方法首先利用点割集或割点把原问题分解成多个子图,然后对每个子图并行求最短路径,最后通过点割集或割点求出整个原问题的最短路径,从而降低算法的时间复杂度,提高算法的效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张清华	重庆邮电大学计算机科学与技术研究所	69	1122	17.0	32.0
5	李鸿	重庆邮电大学计算机科学与技术研究所	3	11	2.0	3.0
6	沈文	重庆邮电大学计算机科学与技术研究所	1	3	1.0	1.0