A Parallel Algorithm of the Shortest Travel Path in Traffic Information Grid
Zhaohui Zhang, Chungang Yan · Journal of Tongji University · 2006
Two parallel algorithms of the shortest travel path,GPSPA1 and GPSPA2 are presented on the basis of a new partition method of road nets.The disadvantages of traditional parallel label algorithms are overcome and heterogeneous cluster can be fit in.The experimental results show that the speedup ratios of the two algorithms are about 3 when a cutter can partition the O?-D completely,and that GPSPA2 is better than GPSPA1 in other cases.GPSPA2 is applied in the version 2.0 of TIG.