algorithmstrees
Given an undirected weighted tree with $n$ vertices, how can I design an algorithm that is $O (n^2)$ and other that is $O(n)$ for finding the longest path between two nodes in the tree (without repeating vertices or edges)?
Intuitively I think that running BFS or DFS twice might work for an $O(n^2)$ algorithm, and Dijkstra's algorithm for $O(n)$ an algorithm. However, I'm not sure how to show that this works (proof or pseudocode), or if it is actually correct.
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.
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$.
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$.
Best Answer
This question may be more appropriate for CS Stack Exchange. Either way, I'll attempt to help out here.
Yes, running BFS/DFS twice will work. We start with an arbitrary node, $u$ and run BFS/DFS to find the farthest node from it, say $v$. We then run BFS/DFS starting with $v$ and find the farthest node from it. This will output the longest path in the tree. Here is a question on CS Stack Exchange that addresses this (and a more efficient) method.
Yes, Dijkstra's will work. Normally, Dijkstra's cannot be used for the longest path due to the possibilities of negative weight cycles, but it can be used here as we're dealing with trees. This is because the longest path between 2 nodes is the same as the shortest path between them (in other words, there is a unique path between any 2 nodes).
Hope that helped :)