Improvement research on Dijkstra shortest path algorithm and its application in GIS-T simulation

摘要：

The Dijkstra algorithm is one of a classical algorithms which to solves the shortest path problem.However,in practice,when we design a special GIS-T information system,there are possibly a large number of poly lines and vertexes in the road linear vector graphics.If we directly make use of this conventional algorithm,we must make the adjacent matrix between one vertex and the other.And it will consume much computing time and storage space,so it is very difficult to be used in the practical project.Therefore,in allusion to the above questions,this paper puts forward an improved method.The contents are as follows: On the one hand,we need to preprocess those complex and unreasonable road network data,and then make a road network topology data file.On the other hand,we combine the topology data file with the Dijkstra algorithm idea that the shortest path is created according to the increasing order of path length.At last,according to this improved method we develop the GIS-T software-1:200,000 scales Shaanxi Provincial GIS-T information system -by using VC++ programming language to make a simulation analysis testing.The result indicates that the method is accurate and highly effective.

关键词： Dijkstra algorithm GIS-T shortest path road network topology VC++ programming language

作者: Yong Zhao Wenhan Dai Qing Wei Yanan Zhang

作者单位: Shaanxi Provincial Highway Survey and Design Institute,Xian,China Xian University of Science & Technology,Xian,China

会议类型: 国际会议

会议名称: The 3rd International Conference on Environmental and Engineering Geophysics(第三届环境与工程地球物理国际会议)

会议地点: 武汉

会议语种:英文

页码: 530-535

在线出版日期: 2008-06-15（万方平台首次上网日期，不代表论文的发表时间）