1
$\begingroup$

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a graph with edge weights 1 but that won't work here.

All I can think of is going for a $O(N^2)$ approach with LCA but thats a glaringly bad approach for huge trees ($N \sim 100000$)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – FrankW
    Commented Jun 24, 2014 at 7:00
  • $\begingroup$ @FrankW True enough, my bad. Thanks for noting; reopening now. $\endgroup$
    – Raphael
    Commented Jun 24, 2014 at 12:24
  • $\begingroup$ Note that you are looking for the diameter of the graph. Try googline that! $\endgroup$
    – Raphael
    Commented Jun 24, 2014 at 12:26
  • $\begingroup$ As stated the question asks for longest paths between any pair of nodes not the maximum over this. $\endgroup$
    – Jernej
    Commented Jun 24, 2014 at 12:51

2 Answers 2

Reset to default
2
$\begingroup$

You can find this path in linear time:

  1. If the tree is unrooted, pick an arbitrary node as root.

  2. Traverse the tree in postorder and for each node:

    2.1. Find the longest and second longest path ending in the current node by maximizing over all children and extending the longest path ending in the child by the edge between parent and child.
    If there are no two children that result in paths of positive length, set the second longest (and if necessary also the longest) path as starting and ending here (length 0).

    2.2. Find the longest path in the subtree that starts at the current node by maximizing over the longest paths in all subtrees below the current one and the path resulting from joining the two paths found in the previous step.

Now the longest path in the subtree started at the root is the one you are looking for.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Frank, isn't he asking about the longest paths between any two nodes? $\endgroup$
    – Jernej
    Commented Jun 24, 2014 at 9:41
  • $\begingroup$ I edited the answer so the algorithm actually considers all pairs. $\endgroup$
    – FrankW
    Commented Jun 24, 2014 at 10:04
  • $\begingroup$ Thanks Frank, I can see how it will work. Working on the code for it. Will mark as correct if I don't find any corner cases. $\endgroup$
    – NitinJ
    Commented Jun 24, 2014 at 10:18
-1
$\begingroup$

Note that the longest path between any two nodes in a tree is also the shortest path (indeed a tree only has one path between any pair of nodes)

Now, you cannot do this in sub-quadratic time since in order to obtain the distances between all pairs of nodes you need to compute $O(n^2)$ of data.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is wrong. See my answer for a linear time algorithm. $\endgroup$
    – FrankW
    Commented Jun 24, 2014 at 10:01
  • $\begingroup$ FrankW could you explain why is this wrong? Somehow I do not see it :( Computing the distances between all vertices of a graph is equivalent to returning a $n \times n$ matrix indexed by the vertices of the tree where the intersection tells you the distance in the graph. Am I missing something? I am of course assuming he is not asking about the diamter (which ofc is doable in linear time) $\endgroup$
    – Jernej
    Commented Jun 24, 2014 at 11:15
  • $\begingroup$ You do not need to explicitly compute all $n\times n$ distances in order to find the longest one. Compare basically every dynamic programming algorithm for an optimization problem. $\endgroup$
    – FrankW
    Commented Jun 24, 2014 at 11:53
  • $\begingroup$ FrankW I guess the original question is kind of vague to me. I thought he was asking about finding the shortest path between ALL pairs of nodes. $\endgroup$
    – Jernej
    Commented Jun 24, 2014 at 12:12
  • 1
    $\begingroup$ The question is asking for the longest (highest-weight) path in the whole tree, not for the longest path between two particular nodes. The latter would be, as you say, equal to the shortest path, since there's exactly one path between any pair of distinct vertices. $\endgroup$
    – David Richerby
    Commented Jun 24, 2014 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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