Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks

The shortest path counting problem is crucial for various applications in road networks, such as network robustness analysis, traffic flow distribution, and navigation optimization. Unlike traditional shortest path problems, it requires enumerating all possible shortest paths, making it computationally challenging, especially in dense urban networks with numerous equal-length paths. Existing methods, such as 2-hop labeling schemes, precompute shortest-path distances and counts for efficient queries but struggle to scale in large networks. In this work, we propose a novel divide-and-conquer approach based on recursive vertex bipartitioning to address this limitation. At its core, we establish a count reconstruction theorem that efficiently combines shortest subpath counts from smaller subgraphs to accurately reconstruct shortest path counts for the entire graph. This approach significantly reduces computational overhead and storage requirements. We also introduce a 2-hop count labeling scheme that integrates effectively with this divide-and-conquer framework. Experimental results show that our approach significantly outperforms state-of-the-art solutions, doubling query processing speed, reducing label construction time to one-fourth, and requiring only around 20% of labeling space.