A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
2026-06-01 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem where you have a special kind of map called a planar graph with directions and weights on the edges, and you want to quickly find the shortest path between any two points even when the weights change over time. They developed a new algorithm that is faster than previous ones when all updates are known in advance (offline), achieving nearly the best possible speed for updating and querying paths. They also created an online algorithm that can handle updates one by one for a version of the problem where weights only increase. Their work partially improves solving this long-standing, difficult problem in both offline and online scenarios.
planar graphdynamic algorithmall-pairs shortest paths (APSP)edge weight updateoffline algorithmonline algorithmworst-case update timeworst-case query timedense distance graphs (DDGs)incremental APSP
Authors
Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Abstract
In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph $G$ undergoes a sequence of edge weight updates and the goal is to maintain a data structure on $G$, that can quickly answer distance queries between any two vertices $x,y \in V(G)$. The currently best algorithms for this problem require $\tilde{O}(n^{2/3})$ worst-case update and query time, while conditional lower bounds show that either update or query time $n^{0.5-δ}$ is needed for any constant $δ> 0$. In this article, we present the first algorithm with near-optimal $\tilde{O}(\sqrt{n})$ worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an \emph{online} algorithm for the incremental APSP problem with $\tilde{O}(\sqrt{n})$ worst-case update/ query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem.