A Shortest Path Analysis Based on Hierarchy

Network analysis is an essential aspect of spatial analysis; and shortest path analysis holds a leading position in network analysis. This paper, on the basis of Dijkstra-based improved algorithm [1], improves data structure by combining hierarchy concept so as to obtain an efficient algorithm with a detailed description of the method. Under VC++6.0 development environment, these two algorithms were compared by taking instance data of Yinmusi lead zinc ore. Experiment result showed the optimal algorithm significantly reduces times of search when the both starting and ending points are in the same layer for a three-dimensional mine tunnel network of steep deposit exploitation; moreover, its execution efficiency outshines the Dijkstra-based improved algorithm so as to perform shortest path analysis via a three-dimensional mine roadway network model with the result of solving problems including mine rescue.