Start at any node, do dfs to find the farthest node from it, then do dfs on that node, calculate distances for every node from that node, then do dfs again, but on node that was farthest in second dfs, calculate distances again, and max distance for any node is max of 2 distances you calculated in dfs for that node.

Auto comment: topic has been updated by youssefbou62 (previous revision, new revision, compare).

The solution relies on finding a diameter, and then using the fact that the maximum distance from any node always goes to one of the endpoints of that diameter. The proof I found has a few cases, but is fairly straightforward if you draw the cases and trace the distances.

a---b---c---d
   /     \
  x       y

I write x-y for the distance between node x and node y. Let a-d be a diameter (so the maximum distance between two nodes). Now assume we want to find the furthest node from x. Take some arbitrary node y, we want to prove x-y $$$\le$$$ max(x-a,x-d). If this is true for all nodes y, then max(x-a,x-d) is the largest distance from node x.

Let x be connected to the diameter at node b, and y be connected to the diameter at node c. Since a-d is the maximum distance between any two nodes (the diameter), b-x $$$\le$$$ min(a-b,b-d), otherwise x-a or x-d would be longer than the diameter. Similarly, c-y $$$\le$$$ min(a-c,c-d).

If b = c (so the path from x to y is not part of the diameter), then:

x-y $$$\le$$$ x-b + c-y $$$\le$$$ x-b + min(a-c,c-d) $$$\le$$$ x-b + c-d $$$\le$$$ max(x-a,x-d).

Otherwise, if a,b,c,d are in that order:

x-y = x-b + b-c + c-y $$$\le$$$ x-b + b-c + min(a-c,c-d) $$$\le$$$ x-b + b-c + c-d = x-d $$$\le$$$ max(x-a,x-d).

Similarly, if the order is a,c,b,d:

x-y = x-b + b-c + c-y $$$\le$$$ x-b + b-c + min(a-c,c-d) $$$\le$$$ x-b + b-c + a-c = x-a $$$\le$$$ max(x-a,x-d).

So in conclusion, for any nodes x and y, x-y $$$\le$$$ max(x-a,x-d), which is what the code computes.

To find the endpoints of a diameter, the code just takes the furthest point from any starting point, twice. It uses the fact that the furthest point from any point x, is an endpoint of a diameter. The proof of this is similar to the above, and can be thought of as proving that x-y = max(x-a,x-d) if and only if y-a or y-b is also a diameter.

Please correct me if you find mistakes.