Abstract:

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 hierarchical 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 optimal solution in theory,but it works faster and can still find the sub-optimal solution more quickly even when data volume is large.

Key words: routing algorithms, shortest path, node constraint, backtracking, greedy algorithm