最短路径算法的并行化策略分析

编号 zgly0001607421

文献类型 期刊论文

文献题名 最短路径算法的并行化策略分析

作者 孙文彬  谭正龙  王江  周长江  何俊芳 

作者单位 中国矿业大学(北京)地球科学与测绘工程学院 

母体文献 地理与地理信息科学 

年卷期 2013年04期

年份 2013 

分类号 TP301.6 

关键词 并行算法  最短路径算法  并行Boost库  网络分割  对向搜索 

文摘内容 常见的最短路径算法多是研究单源多汇或多源多汇问题,针对单源单汇最短路径并行算法的研究较少。为此,该文探讨基于并行Boost库、网络分割、对向搜索的最短路径并行算法;并应用DIMAS提供的路网数据进行了相关实验。结果表明:对向搜索的并行算法效率较高,算法耗时为串行Dijkstra算法的1/4～1/2。