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

摘要

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