Parallel Search Algorithm, Based On The Urban Road Network Shortest Path

With the continuous expansion of the city size, transportation network is more complex, there has been dynamic and large-scale nature of character. With the new features of the network, the shortest path problem has a more important value and significance. With the small-scale of traditional network compared to large-scale networks will appear in hundreds or even tens of thousands of vertices, making the shortest path to solve become more complex, need more computationally. The same time, computing time and required storage space will increase. However, due to the continuous development of computer networks, so that network-based distributed parallel computing technology has been rapid development, there has been a large number of parallel algorithms. So as to quickly solve large-scale networks the shortest path to provide an efficient way.In this paper, basic knowledge of parallel computing had a brief introduction, including the parallel computer model, parallel algorithm design methods and several key factors to improve the parallel algorithms. This paper studies the combination of the contents on urban mass transportation network analysis, feature extraction, and then gives the large-scale urban road network of the macro-and micro models, the establishment of a road network of the graph structure. Then the classical and serial algorithm is designed to parallel Dijkstra algorithm, Using Master/Slave mode, to achieve large-scale network for solving the shortest path fine-grained parallel algorithms, then based on MPI parallel environment and carried out experimental verification, From the theoretical analysis to reduce the complexity of the algorithm from O(N2) to O(N2/p+N*(p-1)),to improve the efficiency of the algorithm. Specific large-scale transportation networks, network partitioning method in parallel the process of solving the shortest path plays a key role. In this paper, several commonly used segmentation method, and their respective advantages and disadvantages are described, Metis graph partition methods used here, to diviser the network. By modifying the Metis library source files, extract useful information for calculating the shortest path. At the same time is given for solving the shortest path parallel hierarchical thinking, and in multi-machine environment, implemented under the shortest path query. On Xi'an-specific electronic map, this article will be divided into two layers to the complexity of the entire road network to simplification, according to the ideological divide and rule, using SPMD model in a distributed environment for parallel solution of shortest paths. Using this method greatly improves the computation efficiency, save the running time, while reducing storage requirements for the computer's memory. Load balancing problem is almost all parallel computing should be considered, This paper also presents a good evaluation function based on the load-balancing strategy and the specific scheduling algorithm, using a parallel quick sort algorithm is verified them, and achieved good experimental results. This method has a very good reference value.Finally a brief introduction of the parallel computing environment based on message passing model of MPI (Message Passing Interface) operating platform, This experiment used four sets to build parallel computing platform for PC, using VC++6.0 to compile the environment, combined with electronic maps of Xi'an, using Mapinfo software to derived map information, in a parallel PC cluster environment to achieve them. The experimental results show that the method at run time and memory space allocation has obvious advantages, has good practicability.