A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Iterative Correcting

A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Iterative Correcting
复制标题

DOI：
10.1109/hpcc.2008.113
复制
发表时间：
2008-09
期刊：
2008 10th IEEE International Conference on High Performance Computing and Communications
影响因子：
--
通讯作者：
Yuxin Tang;Yunquan Zhang;Hu Chen
Yuxin Tang;Yunquan Zhang;Hu Chen
中科院分区：
其他
文献类型：
--
作者：
Yuxin Tang;Yunquan Zhang;Hu Chen

文献摘要

被引文献

相似文献

在本文中，我们专注于满足在智能交通系统中快速找到最短路径的实际需求。提出了一种基于图划分和迭代修正的并行最短路径算法。通过对三个真实的道路网络的测试，我们得出结论：基于图划分和迭代校正的并行算法具有良好的性能。此外，在这些真实的道路网络上，它在IBM集群中的16个处理器上实现了超过15倍的加速。
In this paper, we focus on satisfying the actual demands of quickly finding the shortest paths over real-road networks in an intelligent transportation system. A parallel shortest path algorithm based on graph partitioning and iterative correcting is proposed. After evaluating the algorithm using three real road networks, we conclude that our graph-partitioning and iterative correcting based parallel algorithm has good performance. In addition, it achieves more than a 15-fold speedup on 16 processors in an IBM cluster over these real road networks.