基于网络划分的最优路径并行算法分析与实现

摘要：

最优路径问题是资源分配,线路设计等优化问题的基础,很多问题都可以归结为最优路径问题。求解网络中最优路径的方法可以分为两大类。一种是标号设定算法(label setting, LS),另一种是标号改变算法(label correcting, LC)。由于网络路径算法的应用越来越强调动态性和及时性,因此高效的求解最优路径问题变得越来越重要。在这里,利用一种高效的网络划分方法,实现了基于网络划分的LS/LC并行算法。实验结果表明,基于这种网络划分的并行算法对于求解最优路径有很好的加速比和扩展比。

关键词： 并行算法 最优路径问题 网络划分

作者: 陈虎 唐雨新 张云泉

作者单位: 中国科学院软件研究所并行计算实验室,北京 100080 中国科学院计算机科学国家重点实验室,北京 100080 中国科学院研究生院,北京 100080 中国科学院软件研究所并行计算实验室,北京 100080 中国科学院计算机科学国家重点实验室,北京 100080

会议类型: 国内会议

会议名称: 2007年全国高性能计算学术年会

会议地点: 深圳

会议语种:中文

页码: 274-281

在线出版日期: 2007-10-26（万方平台首次上网日期，不代表论文的发表时间）