关键词: 路网, 最短路径, 异步并行

Abstract: Finding the shortest path is a classic problem with numerous applications. For road networks, it is desirable to find a sufficient short path within a limited period of time, and find a shorter path if there is more time. Since the traditional shortest path algorithms did not consider this constraint when designed, they can not meet the application requirement. To address this issue, an algorithm called APWA*, asynchronous parallelism weighted A*, was proposed, which can respond to users interrupt signal and return to the currently shortest path. Experiments on multiple maps show APWA* can meet the application requirement.

Key words: road network, shortest path, asynchronous parallelism