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
If the two most farthest vertex from
y, and they have the same distance from the vertex
v is a potential center of a diameter. Then we store
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
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
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
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:
The solution I found is this: