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