计算机工程与应用Issue(11)：41-46,6.DOI:10.3778/j.issn.1002-8331.1311-0291
经过指定的中间节点集的最短路径算法
Algorithm for finding shortest path which must go through specified intermediate node set
摘要
Abstract
The vast majority of researches about the shortest path algorithm, nowadays, focus just on the case starting from the beginning point and ending at the ending point. If additional condition that the shortest path must go through some given nodes of which number is uncertain must be met, then most of the existing classic algorithms are not applica-ble. A general method based on the classical Dijkstra algorithm and greedy algorithm is presented to solve this kind of problem. The main method is to split the relevant node set into three sub sets, find the local shortest path of connecting the three subset separately to form the global shortest path to be selected, obtain the target path through screening. The time complexity of the algorithm is given by theoretical analysis and the effectiveness of the algorithm is verified by program-ming calculation.关键词
Dijkstra算法/贪心算法/动态规划/最短路径/相关节点Key words
Dijkstra algorithm/greedy algorithm/dynamic planning/shortest path/pruning algorithm分类
信息技术与安全科学引用本文复制引用
黄书力,胡大裟,蒋玉明..经过指定的中间节点集的最短路径算法[J].计算机工程与应用,2015,(11):41-46,6.基金项目
四川省科技攻关计划项目（No.2012GZ0090）。 （）
