# Longest path with at most $k$ edges in a tree

How to find the longest (in terms of sum of weights) simple path with at most $k$ edges in a tree? Weights of edges are integers, so they can be negative. I thought about using Bellman-Ford, but it would take too much time. Is there any faster algorithm than $O(V \cdot E)$?

• What does the "in a tree" constraint mean? I think you might have packed too much into that sentence for me to understand the problem statement. Can you edit to clarify, e.g., by breaking it down into multiple smaller sentences? Also, can you edit the question to show how you would use Bellman-Ford to solve this problem? – D.W. Jan 18 '16 at 17:19
• The fact that you use Bellman-Ford and talk about "E" doesn't add up with the tree part. Is it actually a tree and you want better time than $O(N ^ 2)$? If that's the case, there is an $O(N log N)$ solution that uses divide and conquer. – Mihai Calancea Jan 19 '16 at 16:50

## 1 Answer

Have you tried looking at the Shortest Path Faster Algorithm (SPFA)? Even though its worst case time is the same as for Bellman-Ford, the average time complexity on a random graph is $O(|E|)$ and it also works for graphs with non-negative edges.