交通信息网格中的最短出行路径并行算法

摘要

根据城市路网的特点,提出了一种新的路网图的分割方法;在此基础上,提出两种网格最短路径并行算法GPSPA1和GPSPA2.这两种算法克服了传统并行标签算法只适合在共享内存的并行机器上使用的缺点,适合网格环境下使用.实验结果表明:分割器不能完全分割源点和目标点时,GPSPA2比GPSPA1效率高;完全分割时,两种并行算法的加速比大约都是3.GPSPA2应用于交通信息服务网格系统2.0版中.