  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$
varies in $(-\infty,+\infty)$, the piece-wise linear cost of the shortest path
from $s$ to $t$ has $n^{\Omega(\log n)}$ pieces. This shows that lower bounds
obtained earlier by Carstensen (1983) and Mulmuley \& Shah (2001) for general
graphs also hold for planar graphs, thereby refuting a conjecture of Nikolova
(2009). Gusfield (1980) and Dean (2009) showed that the number of pieces for
every $n$-vertex graph with linear edge weights is $n^{\log n + O(1)}$. We
generalize this result in two ways. (i) If the edge weights vary as a
polynomial of degree at most $d$, then the number of pieces is $n^{\log n +
(\alpha(n)+O(1))^d}$, where $\alpha(n)$ is the slow growing inverse Ackermann
function. (ii) If the edge weights are linear forms of three parameters, then
the number of pieces, appropriately defined for $\mathbb{R}^3$, is $n^{(\log
n)^2+O(\log n)}$.
