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

A Hierarchical Dijkstra Algorithm for Solving Shortest Path from Constrained Nodes

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

In order to obtain the shortest path from constrained nodes, a hierarchical Dijkstra algorithm is proposed on the basis of backtracking, which is able to find the global shortest path or the second shortest path by searching the local optimal solution within hierarchical structures. Moreover, this algorithm takes full advantage of the hierar-chical structures in saving search progress to realize such operations as the saving and backtracking of the search progress during the searching of the shortest path. Experimental results show that the proposed algorithm increases space complexity slightly, but it can reduce the calls of Dijkstra algorithm effectively, and that, as compared with depth-first search algorithm and geometric algebra algorithm, the proposed algorithm may not always find the opti-mal solution in theory, but it works faster and can still find the sub-optimal solution more quickly even when data volume is large.