计算机应用与软件2011，Vol.28Issue(12)：32-34,3.
求解多段图问题的并行动态规划算法
PARALLEL DYNAMIC PROGRAMMING ALGORITHM FOR MULTISTAGE GRAPH PROBLEM
摘要
Abstract
Multistage graph problem is a special single-source shortest path problem. Based on two kinds of implementations of sequential dynamic programming method, two parallel algorithms with vertex-number-based task partition in cluster are given. Both of them are implemented by MPI. Experimental results indicated that these algorithms have lower time and communication complexity and higher speedup ratio. The algorithms can also be used in any structure of cluster and is of high universality.关键词
并行算法/多段图问题/最短路径/动态规划/集群Key words
Parallel algorithm/Multistage graph problem/Shortest path/Dynamic programming/Cluster分类
信息技术与安全科学引用本文复制引用
崔焕庆,王英龙..求解多段图问题的并行动态规划算法[J].计算机应用与软件,2011,28(12):32-34,3.基金项目
国家自然科学基金(60773034) （60773034）
山东省科技攻关项目(2007GG2QT01007) （2007GG2QT01007）
山东省自然科学基金(ZR2009GQ002,ZR2010FQ014) （ZR2009GQ002,ZR2010FQ014）
