Finding the longest path in a tree

Question

Give a linear time algorithm that, given an undirected tree T = (V,E) with edges weights w, returns the weight of the heaviest path in T.

This is basically asking to do the exact opposite of what the Floyd-Warshall algorithm does. Any suggestions (or even solution) as to how to approach/solve this question?

Answer 1

You should use Dynamic Programming to solve this problem. Make the tree rooted from arbitrary vertex. Then for each subtree find the maximum weighted path from root of that subtree to other nodes.

Answer 2

You could use a simple DFS algorithm and returning a tuple (int,int) where the first value means "The heaviest path ending or beginning in this node" and the second "The heaviest path in this subtree".

This solutions has the same time complexity than DFS and that is O(N+M). In this case, we know the graph is a tree, so M = N-1 and it ends in O(N).