Dynamic updates speed up finding multiple shortest simple paths
Towards Dynamic Top-$k$ Simple Shortest Paths
Data Structures and Algorithms
Summary
Finding the top-k shortest simple paths between two points in a network is useful but can be slow when you need to change the number of paths (k) quickly. The authors introduce a new way to store and update these paths efficiently using a structure they call a pseudo-tree. Their method reuses previously found paths and adjusts to new path counts without starting from scratch every time. This approach greatly reduces computation time in practical settings, especially when k changes frequently.
What this means in practice
- •For network operators: Update routing options dynamically when network conditions or requirements change without recomputing paths from scratch.
- •For transportation planners: Quickly revise alternative routes in response to varying constraints or objectives by efficiently updating a set of best simple paths.
Authors
Gianlorenzo D'Angelo, Andrea D'Ascenzo, Mattia D'Emidio, Gabriele Di Stefano, Marta Innamorati
Abstract
Computing the top-$k$ \textit{simple} shortest paths between two vertices of a graph, i.e., solving the P-KSSP problem, is a fundamental primitive in graph analytics. In modern scenarios, however, queries are rarely one-shot: parameters change as applications adapt their information needs, and recomputing a solution from scratch at every request quickly becomes a bottleneck. We study P-KSSP in a dynamic setting, focusing on changes of the parameter $k$: given a top-$k$ solution for a pair of vertices and a new value $k'$, the goal is to compute a top-$k'$ solution reusing the previously computed paths. Our approach rests on the \textit{pseudo-tree}, a compact representation of a collection of simple $s$--$t$ paths: we show that building it from an arbitrary, unstructured solution amounts to trie construction, and give two constructions running in time linear in the size of the collection. On top of it, we design UPD, a dynamic algorithm that updates a solution upon a change of $k$; we prove its correctness, analyze its complexity, and show that it is a general, solver-agnostic scheme, which starts from the paths alone, is parametric in the routine that generates candidate paths and combinable with known preprocessing techniques, as well as with an online pruning rule that we formalize. While a worst-case update is asymptotically comparable to recomputing from scratch, an extensive experimental evaluation shows that a variant of UPD is the fastest method in the large majority of tested configurations, often by a wide margin (with speedups over recomputation that grow with $k$ and $k'$ and exceed $60\times$), yielding a practical recipe for the configuration to deploy.