Recovering a Weighted Graph from Shortest Path Distances 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. 
 A: Here's a counterexample for (A).  Let $V=\{0,1,2\}$, let $E$ consist of $\{0,1\}$ and $\{1,2\}$, each with weight 1.  The shortest-path metric would be unchanged if we add a third edge $\{0,2\}$ with weight $2$.
A: Andreas Blass has produced a simple counterexample to (A) in his answer. I suspect that if your graph is flat in the sense of Andrew Stacey's answer here, then you can in fact recover it from the pairwise distances alone by embedding it a sufficiently high-dimensional Euclidean space.
You can find a nice approximation scheme for question (B) in the paper "Representing graph metrics with fewest edges" by Feder et. al., available here. The basic idea is to add new "Steiner" vertices while removing superfluous edges. The introduction, which is remarkably well-written, contains an overview of how the problem is NP hard, and who did what in which paper, etc. Note that the scheme suggested by Andreas in the comments to his answer does not guarantee that the remaining graph is sparsest possible independent of the order in which the edges are processed.
This is a fairly old problem, and the literature goes back at least to Hakimi and Yau's 1964 paper "The distance matrix of a graph and its realizability". I wasn't able to find a free copy, but you can admire the paywall here.
