We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ ... more >>>

We study shortest paths in directed graphs whose edge weights are of the form $$wt(e) = a_{e,1} \lambda_1 + a_{e,2} \lambda_2 + a_{e,3} \lambda_3 + \cdots + a_{e,d} \lambda_d + a_{e,d+1}.$$
Here, each $a_{e,i}\in\mathbb{R}$ is a fixed constant for each edge $e$, whereas each $\lambda_i$ is a shared variable ... more >>>