Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Engineering
Shortest Path Calculation Using Contraction Hierarchy Graph Algorithms On Nvidia Gpus, Roozbeh Karimi
Shortest Path Calculation Using Contraction Hierarchy Graph Algorithms On Nvidia Gpus, Roozbeh Karimi
LSU Doctoral Dissertations
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 …