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 an $O(n)$ algorithm. I'm new into this kind of analysis so I'm not sure how to show that this works (proof or pseudocode), or if this is actually correct.


Browse other questions tagged or ask your own question.