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)
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:
![ShortestPathsTerrain][1]
One can almost see runoffs and rivers—terrain shortest paths are quite ... geophysical.