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

摘要：

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

关键词：割点、最短路径算法、Dijkstra算法、并行计算、粒计算

所属期刊栏目：33

分类号：TP301.6(计算技术、计算机技术)

资助基金：重庆市教委科学技术研究项目KJ110512;重庆市教委教改项目103161;重庆邮电大学研究生教育创新计划资助项目Y201110

在线出版日期：2012-12-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：125-129