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

摘要

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