Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest paths where the length of the path is equal to sum of all edges weights.

I know that in a tree there is only one simple path between every pair of nodes. So, even if you try every pair of nodes finding the path between then, you would have an $O(n^3)$ algorithm.

A better way is to find for every node the cost to every other node in a single visit. This lowers the algorithm to $O(n^2)$.

Is there any algorithm that runs in linear time?

• One can also observe the quadratic algorithm is essentially an application of Bellman-Ford.
– Juho
Feb 19 '15 at 13:16

Order the tree, so we can speak about a node and its subtrees. Now evaluate the tree recursively. In each node keep track of two values: (1) the value of the optimal path below the node (starting and ending somewhere below in the subtrees), and (2) the value of the optimal path below that additionally ends in the node itself.

• Would u please add a bit detail?, i dont get it. in O(n)? Feb 19 '15 at 13:00
• It seems "my" solution is what is actually the method in the answer linked by Raphael. Study it. Yes, linear. Feb 19 '15 at 21:48

Since trees are acyclic graphs, we can find longest and shortest (simple) paths, with or without negative weight with the same basic algorithmic idea, changing only which path to prefer.

Hence, this recursive solution for finding the diameter of trees carries over with minor changes.

• would you please correct me ? Feb 19 '15 at 15:40
• @M.holi I suspect that this is coursework, so no, I won't give you more detail. I also think the answer I link is sufficiently detailed (in fact, more detailed than I'd give it for a "homework" question), and I consider the necessary changes to be simple enough. I suggest you think about it for more than a few minutes, and try some examples.
– Raphael
Feb 19 '15 at 15:48
• this is not coursework. i'm not sure about linearity? Feb 19 '15 at 15:55
• @M.holi I am. Go analyse the algorithm I link to.
– Raphael
Feb 19 '15 at 15:58