We construct a family of planar graphs {G-n}-n≥4, where G-n has n vertices including a source vertex s, a sink vertex t, and edge weights that change linearly with a parameter λ such that, as λ varies in (-∞,+∞), the piece-wise linear cost of the shortest path from s to t has nΩ(logn) pieces. This shows that lower bounds obtained by Carstensen (1983) and Mulmuley & Shah (2001) for general graphs also hold for planar graphs, 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 nlog 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 nlog n+(α(n)+O(1))d, where α(n) is the inverse Ackermann function. (ii) If the edge weights are linear forms of three parameters, then the number of pieces, appropriately defined for R3, is n (log n)2+O(log n). © 2019 IEEE.