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.