基于CUDA的并行联程路径搜索算法

摘要

随着民航业的蓬勃发展,形成了庞大的航线网络,在众多城市间有很多航线可供选择.如何快速地从如此庞大的网络中得到K条最短路径(K-Shortest-Path,简称KSP)成了联程路径搜索的瓶颈.采用Yen算法求解航线网络中的KSP问题,并在CUDA平台下实现其并行化.并行的基本策略是借助GPU平台并行的松弛每个节点的相关边.最后,通过在CUDA平台下的实验结果表明,与串行Yen算法计算相比,基于CUDA的并行Yen的计算速度得到了很大的提高.