I am interested in the following problem (A) and its related formulation (B). (A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), \forall v,v'\in V$, where $d_G(\cdot,\cdot)$ is the shortest path metric with respect to $G$. Can one recover the structure (i.e., the edge set $E$ and the weights $w$) of $G$ from just this distance information?

(B) Given a finite metric $(V,d)$, find the *sparsest* weighted graph $G=(V,E,w)$ that is consistent with $d$ in the sense that $d_G$ is the same as $d$.

I am curious to know if these problems or similar ones have been studied and have interesting answers.

learner(i.e., the algorithm that is trying to recover the graph) such that this becomes possible? – Skoro Jun 30 '13 at 13:40