1
$\begingroup$

I'm trying to find from a undirected weighted tree of only positive weights the longest path (diameter of a tree, I'm told?) I know the most common algorithm is one where you pick a random node $x$, use DFS from that node to find the longest path which ends with node $y$ and once again from $y$ using DFS find the longest path which ends in $z$. $(y,z)$ should then be the longest path.

However, I was wondering if this another algorithm I thought of would work (and with the same complexity of $O(|V|)$

  1. Find the longest edge in graph $e$

  2. $e$ joins 2 nodes $a$ and $b$. Considering both $a$ and $b$ to be root of their respective subtrees, run DFS on both $a$ and $b$ and find the longest path $A$ and $B$ which end with the node $a_{end}$ and $b_{end}$ respectively.

  3. $(a_{end}, b_{end})$ is the longest path.

My reason was the longest path of the graph has to contain the edge with the heaviest weighting. Is that a correct assumption? Also, the algorithm is still of complexity $O(|V|)$ since step 1. is $O(|V|)$, step 2 for DFS on $a$ is $O(|V|)$ and DFS on $b$ is $O(|V|)$. That probably isn't so efficient compared to the standard algorithm but it should adhere to the said requirements I guess?

$\endgroup$

1 Answer 1

3
$\begingroup$

Your assumption is false, this is a counterexample:

enter image description here

Check, that the longest path (all black edges) has weight $6$, while any path containg the red edge has at most weight $5$.

$\endgroup$
5
  • $\begingroup$ Yea I kinda found a counterexample too to my algorithm a while after I posted. Thanks anyway! $\endgroup$
    – Jon Gan
    Jul 7, 2013 at 17:58
  • $\begingroup$ @mercurial Tomas still answered your question. I think it would be polite to upvote and accept the answer. $\endgroup$ Jul 7, 2013 at 18:01
  • $\begingroup$ @VedranŠego yea was going to do so directly after commenting but was told to wait a minute :) $\endgroup$
    – Jon Gan
    Jul 7, 2013 at 18:04
  • $\begingroup$ Ah, bad timing on my side then. Took me a while to read it all, so whene there was still no green checkmark, I thought you forgot. I apologize for the mistake. $\endgroup$ Jul 7, 2013 at 18:08
  • $\begingroup$ Well, thanks for the checkmark, you are rewarded with a better picture ;) $\endgroup$
    – Tomas
    Jul 7, 2013 at 18:22

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.