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|)$
-
Find the longest edge in graph $e$
-
$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.
- $(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?
Best Answer
Your assumption is false, this is a counterexample:
Check, that the longest path (all black edges) has weight $6$, while any path containg the red edge has at most weight $5$.