Parametric Shortest Paths in a Linearly Interpolated Graph

Abstract

We consider the parametric shortest paths problem in a linearly interpolated graph. Given two positively-weighted directed graphs $G_0=(V,E,\ddot{I}{‰}_0)$ and $G_1=(V,E,\ddot{I}{‰}_1),$ the linearly interpolated graph is the family of graphs $(1-\hat{I}»)G_0+\hat{I}»G_1$, parameterized by $\hat{I}»\in [0,1]$. The problem is to compute all distinct parametric shortest paths. We compute a data structure in $\hat{I}˜(k|E|\log |V|)$ time, where~$k$ is the number of distinct parametric shortest paths over all~$\hat{I}»\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~$\hat{I}˜(\log k)$ time.

7 pages, 2 figures. Presented at CG Week Young Researchers Forum 2026