I have a tree where each edge is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the sum of the weights of the edges in the path is maximum). There's no restriction on what node the path starts or ends.
I have a possible algorithm, but I am not sure it works and I am looking for a proof. Here it is:
- Select an arbitrary node u and run DFS(u) to find the maximum weight simple path that starts at u. Let (u, v) be this path.
- Run DFS(v) to find the maximum weight simple path that starts at v. Let this path be (v, z).
Then (v, z) is a simple path of maximum weight. This algorithm is linear in the size of the graph. Can anyone tell me if it works, and if so, give a proof?
Note: The Longest Path Problem is NP-Hard for a general graph with cycles. However, I only consider trees here.