CUDA-based Parallel Interline Path-searched Algorithm
Jianfu Li · Intelligent Computer and Applications · 2013
With the vigorous development of the civil aviation industry,there has already formed an extensive route network,and there are many routes to choose from between the same cities taken-off and landed.How quickly to find K shortest paths(K-Shortest-Path,KSP) becomes a bottleneck of interline path-searched algorithm in such a large network.This article adopts the Yen algorithm to solve the KSP problem in the route network,and to achieve its parallelism in CUDA platform.The basic parallel strategy is to use the classic algorithm for finding the shortest path,then according to the Yen algorithm proposing restrictions to define deviated nodes,and finally departing from nodes parallel multi-core graphics to find candidate paths.On the basis of the aboved process,the experimental results show that compared with the serial Yen algorithm,calculation speed of parallel Yen based on the the CUDA greatly improves.