I've been asked to find a path between two vertices on a complete graph, say A and B. Each edge has a weight, and the path needs to travel from A to B. However the problem is not to determine the shortest distance, but a path that minimises the average of the distances (which is defined as the total distance divided by the number of edges) and if possible minimises the standard deviation of the distances.
For example if A to B direct is 3, but A to C to B is 5, this would result in an average of 2.5.