GPU road network graph contraction and SSSP query
Roozbeh Karimi, David M. Koppelman, Chris J. Michael · 2019
PHAST is to date one of the fastest algorithms for performing single source shortest path (SSSP) queries on road-network graphs. PHAST operates on graphs produced in part using Geisberger's contraction hierarchy (CH) algorithm. Producing these graphs is time consuming, limiting PHAST's usefulness when graphs are not available in advance. CH iteratively assigns scores to nodes, contracts (removes) the highest-scoring node, and adds shortcut edges to preserve distances. Iteration stops when only one node remains. Scoring and contraction rely on a witness path search (WPS) of nearby nodes. Little work has been reported on parallel and especially GPU CH algorithms. This is perhaps due to issues such as the validity of simultaneous potentially overlapping searches, score staleness, and parallel graph updates.