3
$\begingroup$

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?

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

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.

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

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.

$\endgroup$
  • $\begingroup$ would you please correct me ? $\endgroup$ – M. holi Feb 19 '15 at 15:40
  • $\begingroup$ @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. $\endgroup$ – Raphael Feb 19 '15 at 15:48
  • $\begingroup$ this is not coursework. i'm not sure about linearity? $\endgroup$ – M. holi Feb 19 '15 at 15:55
  • $\begingroup$ @M.holi I am. Go analyse the algorithm I link to. $\endgroup$ – Raphael Feb 19 '15 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.