Parametric Shortest Paths in a Linearly Interpolated Graph
2026-04-10 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study a problem where you have two versions of a directed graph with weights on edges, and you blend them together by a parameter that goes from 0 to 1. They want to find all shortest paths that can appear as the parameter changes, since different paths might be shortest at different points. The authors create a data structure that efficiently records all these shortest paths, allowing quick answers to shortest path queries for any parameter value. Their method takes time proportional to the number of distinct shortest paths times the graph size and allows fast queries afterward.
parametric shortest pathsdirected graphlinearly interpolated graphedge weightsdata structuretime complexityshortest path querylinear interpolationgraph algorithms
Authors
Jacob Sriraman, Eli Barton, Brittany Terese Fasy, David L. Millman, Brendan Mumey, Nate Rengo, Braeden Sopp, Vasishta Tumuluri, Binhai Zhu
Abstract
We consider the parametric shortest paths problem in a linearly interpolated graph. Given two positively-weighted directed graphs $G_0=(V,E,ω_0)$ and $G_1=(V,E,ω_1),$ the linearly interpolated graph is the family of graphs $(1-λ)G_0+λG_1$, parameterized by $λ\in [0,1]$. The problem is to compute all distinct parametric shortest paths. We compute a data structure in $Θ(k|E|\log |V|)$ time, where~$k$ is the number of distinct parametric shortest paths over all~$λ\in [0,1]$ that exist for a nontrivial interval of parameters, each corresponding to a linear function in a maximal sub-interval of $[0,1]$. Using this data structure, a shortest path query takes~$Θ(\log k)$ time.