Physical Sciences and Mathematics Commons^™

Efficient Navigation For Constrained Shortest Path With Adaptive Expansion Control, Wenwen Xia, Yuchen Li, Wentian Guo, Shenghong Li

Research Collection School Of Computing and Information Systems

In many route planning applications, finding constrained shortest paths (CSP) is an important and fundamental problem. CSP aims to find the shortest path between two nodes on a graph while satisfying a path constraint. Solving CSPs requires a large search space and is prohibitively slow on large graphs, even with the state-of-the-art parallel solution on GPUs. The reason lies in the lack of effective navigational information and pruning strategies in the search procedure. In this paper, we propose SPEC, a Shortest Path Enhanced approach for solving the exact CSP problem. Our design rationales of SPEC rely on the observation that …