Study and Implement of Shortest Path Parallel Algorithms with Two Strategies
Jun Zhi-cai · Journal of systems management · 2006
With the research and application of Intelligent Transportation System,there is a higher requirement for solving the shortest path problem in large scale transportation networks in real time.To find out the effective shortest path parallel algorithms for the actual transportation networks,three labeling shortest path algorithms are firstly chosen to be parallelized.The parallel shortest path algorithms are then implemented based on both network duplication strategy and network partition strategy.The speed-up ratio and efficiency of parallel algorithms are then tested and analyzed in both actual road networks which are obtained from the transportation planning software based on GIS,TransCAD,and grid networks of different scales which are generated randomly.From the results,it is concluded that the speed-up ratio of two-queue label-correcting parallel algorithm with the strategy of network partition can reach(6.32),when solving the shortest path problem of 32 sources in actual transportation network including (5 181) nodes on eight computers.It also shows similar excellent speed-up and scalability in other test networks.