Constructing a minimum spanning tree from an all-shortest path graph?

Question

Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a connected network $T$ of $n$ nodes and $n-1$ edges - i.e. the shortest path distance between two nodes in $T$.

About the network $T$:

• There are exactly $n$ nodes and $n-1$ edges.
• The network is one connected component, thus it is a tree.
• All edges have positive length.

My problem is that if I compute a minimum spanning tree $T'$ of $G(D)$ using, for instance, Kruskal's algorithm will the resulting tree $T'= T$?

• I tried to argue that they are indeed equal, because if we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

I am not sure if this argument holds. How can I argue that $T' = T$?

Answer 1

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me continue your approach.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$.

Consider $t_0$, the point of time when edge $(u,v)$ had been determined to be part of $T'$ but had not been added to $T'$ yet by Kruskal's algorithm. At time $t_0$, for all $0\le i\le k-1$, $(u_i, u_{i+1})$, an edge that is shorter than $(u,v)$ must have been tried, which meant node $u_i$ and $u_{i+1}$ must have been connected by a path in $K(t_0)$, the edges of $G(D)$ that had been determined to be part of $T'$ at time $t_0$. That means before $t_0$, node $u$ and $v$ had been connected by a path in $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

---

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.