Inferring tree graph from distance matrix

Question

Given a $n$x$n$ distance matrix of some undirected weighted tree graph, is it possible to infer the underlying tree and its edge weights?

For example, suppose we are given the following distance matrix \begin{pmatrix} 0 & 1 & 4 & 5 & 6 \\ 1 & 0 & 3 & 4 & 5 \\ 4 & 3 & 0 & 1 & 2 \\ 5 & 4 & 1 & 0 & 3 \\ 6 & 5 & 2 & 3 & 0 \end{pmatrix} Assuming strictly positive weights, we know that in each row every minimum corresponds to an edge and its weight, i.e. $1 \leftrightarrow 2$, $3\leftrightarrow 4$ and $3 \leftrightarrow 5$. From there, it's easy to determine that the underlying weighted adjacency graph is given by \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 0 & 3 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \end{pmatrix} How to solve this problem in general for strictly positive weights?

Answer 1

The following greedy algorithm should reconstruct the tree corresponding to a given distance matrix $M$, assuming it exists.

Beforehand, one must show that $T$, if it exists, is unique, but unless you insist I will skip these details (informally, you can use induction on $n$: from a tree $T$ for $M$, remove a leaf $l$, use induction to get the unique tree for $M$ with the $l$ row/column removed, then show that there is only one unique place to plug back $l$).

Start with $F$ as the forest on $n$ vertices and no edge.

While $F$ is not a tree:

Choose $u$ and $v$ such that $u$ and $v$ are in two different connected components of $F$ and $M_{u, v}$ is minimum among all possible choices.

Add $uv$ to $F$ and set its weight to $M_{u, v}$

Suppose that we do not obtain a tree with distance matrix $M$ after running the algorithm, but that such a tree $T$ exists.

Let $uv$ be the first inserted (weighted) edge such that $uv$ does not belong to $T$ (observe that if $uv$ belongs to $T$, its weight must be correct). Let $F$ be the forest obtained from the algorithm before inserting $uv$, and for a vertex $x$, denote by $C(x)$ the connected component of $F$ containing $x$. Note that $C(u) \neq C(v)$.

Now, let $z$ be the neighbour of $u$ on the path from $u$ to $v$ in $T$. We have $d(u, v) = d(u, z) + d(v, z)$, implying $d(v, z) < d(u, v)$ (assuming strictly positive weights). If $C(v) \neq C(z)$, the algorithm would have chosen the $vz$ edge instead of $uv$, so assume $C(v) = C(z)$. But then, $C(u) \neq C(z)$ and $d(u, z) < d(u, v)$, again contradicting the choice of the algorithm. Therefore the $uv$ edge is correct.

Of course, there is no guarantee that the algorithm reflects the distances of $M$, but if that's the case, it means that no tree exists for $M$.