Find the longest path in a tree when there are weights on edges

I am looking for an efficient algorithm. I would also appreciate a clean analysis of the same.开发者_StackOverflow中文版

The answer is closely related to this question that appeared on SO last week. Instead of looking for a subsection of an array, you'll want to find the subsection of a tree.

I think it should be sufficient to start with the left-most end node and traverse your way up and down the tree towards the right-most end node keeping track of the largest path-sum and the current path-sum in the same way the solution in the linked question keeps track of the sums within an array.

Dijkstra's algorithm is pretty good for this case.

Without working off of any details, a simple DFS search should work

dfs( node, score ):
    max = 0; maxv = None
    for each edge in node
         [val,path]  = dfs( edge.child, edge.cost )
         if(val>max)
             max = val; maxv = path + [node]
    return [max,maxv]

EDIT - Since there seems to be some confusion here, let me explain further. We can talk about 2 different problems, the first is that we consider this a tree interpreted as a DAG with a single root and a path starts at the root and takes a single path from that root. In this case, the function is called as dfs( root, 0 ). In this case, are essentially building up a maximum cost for each node choosing either to

• A) Take one of the nodes as a path or
• B) Take no path, since all paths lead to a negative utility

The second problem is that the tree is not a DAG (proposed by Vlad) In this case we can start at any node and end at any node. Since there are no cycles in a tree, we can run an algorithm like Floyd-Warshall to find the longest path amongst all pairs.

Floyd-Warshall is roughly equivalent to memoziation of the routine above. If we add an additional parameter to keep track of the starting node, and try every starting node, paths will be reused. There may be a better way to exploit the structure of the tree, I'll think about that.

Example as proposed by Vlad (see comments for response)

             *
          1 / \ 1
           *   *
        -1/
         *

I think BFS may be the right approach for this problem bcoz none of the branched paths will have a common node (This is obvious coz its a tree).

IDEA: During the return of the BFS at each step we can return the max length from the branching node to the children. But for the first call of BFS i.e for the root node we need to collect the max and second max path lengths, add them up this is the max distance required for the answer. If there are no multiple branches at the root node then the max distance is from the root node.

Code for the above algorithm:

int BFS(vertex V){

    max_dist_to_children = INT_MIN;

    // Here by parent i refer to the previous vertex
    // through which V is explored (There will be only one parent, think!!)
    for v in (neighbor(V) and v!=V.parent){
        v.parent = V;
        dist = BFS(v);

        if dist > max_dist_to_children:
           max_dist_to_children = dist;
     }

     return dist;
}

The first call of BFS from root node is a bit different from the above as the first call has to return the sum(max_distance, second_max_distance).