Research On The Algorithm For Shortest Path Problem In Complicated Network

With the development of computer science and geographical information science, geographical information system has been used widely and deeply because of its strong spatial analysis function. GIS, GPS etc. techniques have been widely applied to the Intelligent Transportation System (ITS) on a global scale. Network analysis in GIS is one of the most important functions and the key issue of network analysis is the shortest path problem. Therefore, the study of the shortest path algorithms which are used to find and provide one or more rapid, economic, convenient shortest paths from start to destination in urban public traffic network, is the most basic and most crucial problem, is also a research project that cannot be ignored in the city information-based construction, is also the urgent request of building the ITS which is modernization and has the power of controlling by making use of various new and artificial intelligent techniques.This paper focuses on the optimization problems about complicated network and carries on a research to the shortest path problem and K-shortest path problem considering the urban public traffic as background. Firstly, by analyzing the characteristics of the urban public traffic network the diagram is abstracted reasonably from it according to the principle of topology and the diagram is a multi-graph. In order to find the solution in multi-graph, this paper proposes an improved algorithm based on A* considering of the fault of others. And then the KSPA algorithm is designed to solve the K-shortest paths problem based on the improved algorithm. Experimental results show the improved algorithm and KSPA maintains an excellent efficiency. The KSPA algorithm can be used to solve the K-shortest path problems in multi-graph.