  Given a graph, the shortest-path problem requires finding a sequence of edges
with minimum cumulative length that connects a source to a target vertex. We
consider a generalization of this classical problem in which the position of
each vertex in the graph is a continuous decision variable, constrained to lie
in a corresponding convex set. The length of an edge is then defined as a
convex function of the positions of the vertices it connects. Problems of this
form arise naturally in road networks, robot navigation, and even optimal
control of hybrid dynamical systems. The price for such a wide applicability is
the complexity of this problem, which is easily seen to be NP-hard. Our main
contribution is a strong mixed-integer convex formulation based on perspective
functions. This formulation has a very tight convex relaxation and allows to
efficiently find globally-optimal paths in large graphs and in high-dimensional
spaces.
