  Given a graph, the shortest-path problem requires finding a sequence of edges
with minimum cumulative length that connects a source vertex to a target
vertex. We consider a variant of this classical problem in which the position
of each vertex in the graph is a continuous decision variable constrained in a
convex set, and the length of an edge is a convex function of the position of
its endpoints. Problems of this form arise naturally in many areas, from motion
planning of autonomous vehicles to optimal control of hybrid 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 and lightweight
mixed-integer convex formulation based on perspective operators, that makes it
possible to efficiently find globally optimal paths in large graphs and in
high-dimensional spaces.
