Finding the longest path in an undirected weighted tree

Solution 1:

Consider the following algorithm, where we start at terminal nodes and keep removing them while accounting for the corresponding paths. For each node $v$, we store $2$ longest paths we have obtained so far (say of length $l_1(v)$ and $l_2(v)$, with $l_1 \geq l_2$), which end at that node. Initially set all these values to zero.

1. Let $v$ a terminal vertex in the tree and let $(u,v)$ be the edge touching it.
2. Set $l = l_1(v) + w(u,v)$.
3. Modify $l_1(u)$ and $l_2(u)$ by picking the largest two among $l_1(u)$, $l_2(u)$ and $l$.
4. Remove the terminal node $v$ and its edge $(u,v)$ from the tree. If the tree is not empty (no edges), go back to step $1$.

When all edges have been removed, we can show that maximum path length is given by $\max {(l_1(v) + l_2(v))}$, over all nodes $v$ in the original tree. Each vertex and edge is visited exactly once and all the operations are constant time, so the algorithm is linear in the number of vertices.

I assumed here that an empty path (path with no edges) is admissible and has length $0$ (for example, when all edge weights are negative, empty path is the longest). But if you only want non-empty paths, you could change the initialization of $l_1$ and $l_2$ values for all nodes to $-\infty$ instead of $0$.

Solution 2:

Good idea. In fact, if all the edge weights are 1, this is a standard way to find the diameter of a tree. Unfortunately, your two-DFS algorithm has a problem when the edge weights can be negative.

Consider, for example, the following edge-weighted tree:

If we do a DFS starting at $u=v_0$ we find that there are two maximal paths from $u$: to $v_1$ and to $v_3$, both with weight 2. Doing the second DFS from $v_1$ yields the maximal path $\langle v_1, v_0, v_2, v_3\rangle$ of weight 4, but doing the DFS from $v_3$ gives the maximal path $\langle v_3, v_2, v_4\rangle$ which has weight 5.

I'm fairly sure you could modify your algorithm so that it gives a maximal path, but I suspect that the modified version would no longer be linear in the number of vertices. Gotta think about that.