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$
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$
  • $\begingroup$ Yea I kinda found a counterexample too to my algorithm a while after I posted. Thanks anyway! $\endgroup$ – mercurial Jul 7 '13 at 17:58
  • $\begingroup$ @mercurial Tomas still answered your question. I think it would be polite to upvote and accept the answer. $\endgroup$ – Vedran Šego Jul 7 '13 at 18:01
  • $\begingroup$ @VedranŠego yea was going to do so directly after commenting but was told to wait a minute :) $\endgroup$ – mercurial Jul 7 '13 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$ – Vedran Šego Jul 7 '13 at 18:08
  • $\begingroup$ Well, thanks for the checkmark, you are rewarded with a better picture ;) $\endgroup$ – Tomas Jul 7 '13 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.