Given a graph embedded in a metric space, its dilation is the maximum over all distinct pairs of vertices of the ratio between their distance in the graph and the metric distance between them. Given such a graph G with n vertices and m edges and consisting of at most two connected components, we consider the problem of augmenting G with an edge such that the resulting graph has minimum dilation. We show that we can find such an edge in O((n^4*log n)/m^{0.5}) time using linear space which solves an open problem of whether a linear-space algorithm with o(n^4) running time exists. We show that O(n^2*log n) time is achievable if G is a simple path or the union of two vertex-disjoint simple paths. Finally, we show how to find an edge that maximizes the dilation of the resulting graph in O(n^3) time with O(n^2) space and in O(n^3*log n) time with linear space.