Optimum addition of an edge to a path

Let Q(G) denote the sum taken over all vertex pairs u,v of a graph G of the shortest distance from u to v in G . We determine the edges e which when added to the path P_m minimize Q(P_{m} + e) . For example, if 1,{\cdots},2n+ 1 is the vertex sequence of P_{2n +1} , the unique optimum edge is e=[a, 2n+2-a] , where a = [n(\sqrt{2} - 1)] .