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
