Research On Parallel Algorithms Of Shortest Path Problems

With the rapid development of intelligent transportation system and communication systems, problems in time dependent networks and large scale networks become more and more important. The study of this kind of problem is of more importance and is much more valuable in real applications. These problems are very complex and computationally intense. If the size of the network is very large, it will be more difficult to solve it. Furthermore, the computing time and the required memory will increase dramatically. Parallel processing provides an effective method to solve large-scale dynamic shortest path problems.In this paper, shortest path problems in dynamic networks and large scale networks are studied, and parallel computing and high performance cluster computing which is focused on are introduced. Then for time-dependent network, the node-decomposing model is devised to divide the network data. And a parallel algorithm for computing shortest paths in time-dependent network is presented. The algorithm can compute the shortest path from each node to a given destination. For large scale network, we use network-tree model to divide the network data and the data is allocated dynamicly. Then a parallel algorithm for computing shortest paths in large scale network is devised using Master/Slave model. This algorithm greatly imporves the computing efficiency and reduces the memory requirement for large scale network optimization.Finally, a parallel computing platform based on PC cluster is constructed. The two parallel algorithms are implemented and tested on this platform. The computing time, speedup and effiency are presented. We also discuss the load balance and the way to improve the performances of parallel algorithms. The computing results show that the parallel algorithms devised in this paper are very efficient in solving shortest path problems in dynamic networks and large scale networks.