Efficient shortest path counting in dynamic road network

Abstract The shortest path counting is an important problem for various applications in road networks, such as traffic analysis, reliability assessment, and navigation services. Existing methods, such as 2-hop labeling schemes, precompute shortest-path distances and counts to enable fast query responses, but they face scalability challenges in large and dynamically changing networks. In this work, we propose an efficient solution, Dynamic Count Labeling (DCL) , for shortest path count queries on dynamic road networks. DCL consists of three key components: a tree hierarchy , a 2-hop count labeling scheme , and a shortcut count graph scheme . The tree hierarchy organizes the network to guide the 2-hop labeling design and ensures efficient query processing by limiting the search space to a small subset of relevant label entries. The shortcut count graph scheme enables efficient construction and dynamic maintenance of the 2-hop labels under edge weight increases and decreases. We further develop dynamic algorithms to update both the shortcut count graph and the 2-hop labels in response to network changes. Additionally, we introduce a parallel version of our algorithms that leverages the label structure for high parallel efficiency. Experimental results demonstrate that DCL can compete with existing approaches for static graphs in terms of construction time, index size and query time, while enabling efficient index updates for dynamic graphs, at a fraction of reconstruction costs.