Exploring Graph Partitioning for Shortest Path Queries on Road Networks

Abstract

Computing the shortest path between two locations in a road network is an important problem that has found numerous applications. The classic solution for the problem is Dijkstra’s algorithm [1]. Although simple and elegant, the algorithm has proven to be inefficient for very large road networks. To address this deficiency of Dijkstra’s algorithm, a plethora of techniques that introduce some preprocessing to reduce the query time have been proposed. In this paper, we propose Partition-based Shortcuts (PbS), a technique based on graph-partitioning which offers fast query processing and supports efficient edge weight updates. We present a shortcut computation scheme, which exploits the traits of a graph partition. We also present a modified version of the bidirectional search [2], which uses the precomputed shortcuts to efficiently answer shortest path queries. Moreover, we introduce the Corridor Matrix (CM), a partition-based structure which is exploited to reduce the search space during the processing of shortest path queries when the source and the target point are close. Finally, we evaluate the performance of our modified algorithm in terms of preprocessing cost and query runtime for various graph partitioning configurations.