I am given a connected graph. I have to construct a spanning tree from the graph, that has minimum diameter.
However, I looked for the solution, and the solution goes like this.
If the diameter of the tree is even, then it must have a center node. Then we try to find the center node by finding all pair shortest path first, and then trying to check every node if it can be a center or not. We do this the following way.
Lets say the current vertex we are checking is called v
.
If the two most farthest vertex from v
is x
and y
, and they have the same distance from the vertex v
then v
is a potential center of a diameter. Then we store ans
= dis[v][x]
+ dis[v][y]
. We find the minimum of such node v
for which dis[v][x] + dis[v][y]
is minimum. Here, dis[v][x]
means the distance from v
to x
.
To avoid the diameter being odd, we introduce new vertex in every edges.
For example if there is an edge like 1-2
then we introduce a new vertex ( let's say 3
) and the edge 1-2
becomes 1-3
and 3-2
.
What I need is a proof of this solution. Why are we taking the minimum of dis[v][x] + dis[v][y]
? How does this guarantees the minimum diameter?
Also, the solution mentioned if the diameter isn't even, then you might want to check the most distanced vertex from v
being x
and y
and as the diameter is odd, |dis[v][x] - dis[v][y]| = 1
this check will not provide a correct answer.
What I am searching for is a formal proof of this.
The problem is listed in UVa Online Judge, Here's the link:
http://uva.onlinejudge.org/external/108/10805.pdf
The solution I found is this:
https://yuting-zhang.github.io/uva/2016/12/21/UVa-10805.html