Constructing efficient data structures (distance oracles) for fast computation of shortest paths and other connectivity measures in graphs has been a promising area of study in computer science [TZ05, PR10, SGNP10]. In this paper, we propose a distance oracle for computing approximate shortest paths and alternate paths in road networks that exploits the existence of small separators in such networks. The existence of a small cut in a graph allows us to partition the graph into balanced components with a small number of inter-component edges. Specifically, we demonstrate the efficacy of our algorithm by using it to find near optimal shortest paths. Our algorithm also has the desired properties of ALT algorithms [Goldberg, Harrelson’05], such as exploring very few edges and fast query times. We further extend our distance oracle to produce multiple alternative routes, and we empirically demonstrate that our method, while exploring few edges, produces high quality alternates with respect to optimality-loss and diversity of paths.

2021 THE WEB CONFERENCE NEWSLETTER
The Web Conference is announcing latest news and developments biweekly or on a monthly basis. We respect The General Data Protection Regulation 2016/679.