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$)

$\endgroup$
  • 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 Jun 24 '14 at 7:00
  • $\begingroup$ @FrankW True enough, my bad. Thanks for noting; reopening now. $\endgroup$ – Raphael Jun 24 '14 at 12:24
  • $\begingroup$ Note that you are looking for the diameter of the graph. Try googline that! $\endgroup$ – Raphael Jun 24 '14 at 12:26
  • $\begingroup$ As stated the question asks for longest paths between any pair of nodes not the maximum over this. $\endgroup$ – Jernej Jun 24 '14 at 12:51
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.

$\endgroup$
  • $\begingroup$ Frank, isn't he asking about the longest paths between any two nodes? $\endgroup$ – Jernej Jun 24 '14 at 9:41
  • $\begingroup$ I edited the answer so the algorithm actually considers all pairs. $\endgroup$ – FrankW Jun 24 '14 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 Jun 24 '14 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.

$\endgroup$
  • $\begingroup$ This is wrong. See my answer for a linear time algorithm. $\endgroup$ – FrankW Jun 24 '14 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 Jun 24 '14 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 Jun 24 '14 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 Jun 24 '14 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 Jun 24 '14 at 19:06

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.