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

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$$?

• What did you find when you worked through some small examples by hand? – D.W. Mar 17 '19 at 15:51

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