节点约束型最短路径的分层Dijkstra算法

摘要：

针对节点约束型最短路径问题,提出了基于回溯法的分层Dijkstra算法,通过分层结构寻找局部最优解来求得全局最优解或次优解.该算法利用分层结构可保存搜索进度的优势,使其在寻找过必经点最短路径时可以实现对搜索进度的保存与回溯等操作.实验结果表明:分层Dijkstra算法虽然增加了一定的空间复杂度,但能有效地减少Dijkstra算法的调用次数;与深度优先搜索、几何代数算法相比,分层Dijkstra算法虽然不一定能找到理论最优解,但出解速度较快,在数据量较大的情况下能快速找到次优解.

关键词：路由算法、最短路径、节点约束型、回溯法、贪心算法

所属期刊栏目：45

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61573151,61105019;广东省自然科学基金资助项目2016A030313468Supported by the National Natural Science Foundation of China61573151,61105019;the Natural Science Foundation of Guangdong Province2016A030313468

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

页数：共8页

页码：66-73