# Building a graph from pairwise distances

I am not familiar with graphs. However, I am curious about a question on graphs. Given a finite set equipped with a metric, is there any studying on the following problem?

Problem: given the metric $d$ for vertexes on $V$, build the undirected graph with the minimum number of edges such that, for each pair of vertices $(v_1, v_2)\in V$, the shortest path from $v_1$ to $v_2$ equals $d(v_1, v_2)$. Is this graph unique?

This kind of graph building would be very important to model depedency of agents on economical dynamic systems.

-
Why don't you just start with a complete graph, then eliminate any edge $(v_1, v_2)$ for which there is a vertex $v_3$ such that $d(v_1,v_3) + d(v_3,v_2) = d(v_1,v_2)$? – Robert Israel Oct 5 '12 at 18:40
Actually I just want to know if this is a known problem or if there is a field of study for this kind of problem. What would be the complexity of your algorithm? I think it is $O(n^2)$ – user38397 Oct 5 '12 at 18:52

Cris, I'm sorry, but I don't understand your point. Since I wrote that $d$ is a metric in mathematical sense, it will always be finite. In other words, I can always construct a graph by combining all vertices. Hence, the problem has always a solution. – user38397 Oct 5 '12 at 21:21