关键词: 最短路径算法, Dijkstra, 三维模型, 巷道网络, 漫游

Abstract: Three dimensional model of mine tunnel can simulate the work scene at the ground mine，the network analysis based on it is very important for coal mine rescue.According to the network's characteristic of mine tunnel，the point and linear elements in the actual measurement data is abstracted to node-arc ADT，which corresponds to the construction of one-dimensional center line and two-dimensional double line tunnel.In the end，three-dimensional model of the mine tunnel is generated by using arch height of the section，wall height and topological relations to assemble the basic unit of laneway model and triangulation.Network analysis adopts Dijkstra algorithm which can adapt to topology changes，to optimize the traditional Dijkstra algorithm in reducing the search nodes and using the adjacency list storage structure，and then analyze the efficiency of the algorithm.Finally，a program is written to test the shortest path algorithm's analysis in the three dimensional model of mine tunnel with obstacles and make it roam in the model.The results show that the algorithm is fast and effective.

Key words: Shortest route algorithm, Dijkstra, 3D model, Tunnel network, Roam