经过指定的中间节点集的最短路径算法

摘要：

目前研究最短路径的算法，多数只是针对从起点出发到达终点的情况。如果限制这条最短路径必须要经过某些指定的中间节点，则现有的一些算法就不再适用了。基于Dijkstra算法和贪心理论，给出了解决此类问题的方法。将相关节点集拆分成三个子集，分别求连通三个子集的局部最短路径，进而形成全局待选最短路径，通过筛选得到目标路径。通过理论分析算法的时间复杂度和实际编程实验确认了该算法的有效性。

关键词：Dijkstra算法、贪心算法、动态规划、最短路径、相关节点

分类号：TP391(计算技术、计算机技术)

资助基金：四川省科技攻关计划项目No.2012GZ0090。

在线出版日期：2015-06-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：41-46