# 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.

• I should have added the following statement to (A): More interestingly, is there some non-trivial a priori information that one can give the learner (i.e., the algorithm that is trying to recover the graph) such that this becomes possible? – Skoro Jun 30 '13 at 13:40

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$.
• Part (B) admits a similarly trivial solution: Start with a complete graph, weighted by the given distances. Then inspect the edges, one after another, and remove any $\{u,v\}$ for which you have edges $\{u,w\}$ and $\{w,v\}$ whose weights add up to the weight of $\{u,v\}$. – Andreas Blass Jun 29 '13 at 15:39
• Thanks for your answer. I guess I am trying to understand if there are interesting restrictions on this problem that have interesting answers. For instance, if we knew a priori that $G$ was a tree, then there is a way to recover $G$ uniquely (compute the minimum spanning tree of the complete weighted graph formed using the pairwise distances). – Skoro Jun 29 '13 at 16:06