0
$\begingroup$

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.

$\endgroup$
2

Browse other questions tagged or ask your own question.