There is quite a large literature on shortest paths on polyhedral surfaces,
where the distance function is either Euclidean distance or more general metrics.
For example, this recent paper extends to convex distance functions:

> Cheng, Siu-Wing, and Jiongxin Jin. "Shortest paths on polyhedral surfaces and terrains." *Proceedings of the 46th Annual ACM Symposium on Theory of Computing*. ACM, 2014.
([ACM link](http://dl.acm.org/citation.cfm?id=2591821))

Here's an example I made with a student (Biliana Kaneva) finding all shortest paths on a terrain (overhead view) from one vertex to every other vertex:
<hr />
&nbsp;
&nbsp;
&nbsp;
&nbsp;
![ShortestPathsTerrain][1]


  [1]: https://i.sstatic.net/PwAk7.gif