我遇到了一个问题，我们要设计一个有效的算法用于查找与重量最轻的一个简单的路径。 （以最小的重量简单的路径）。

I ran into a problem, we want to design an efficient algorithm for finding a simple path with lightest weight. (simple path with minimum weights).

我觉得这不是多项式的解决方案，但有些朋友说可能是O（n）的或为O（n ^ 2）或为O（n LG N）将是...！

i think this is not polynomial solution, but some friends say may be O(n) or O(n^2) or O(n lg n) would be... !

程序员或专家的人，会帮我吗？任何04-0030-03 code？

programmers or expert man, would help me? any pesudocode?

编辑：

输入到这个问题是一个树T与边缘整数权重。权重可以是负的，零或正数。一路径的长度是在该路径的边的权重的总和。路径是简单的，如果没有顶点重复。

The input to this problem is a tree T with integer weights on the edges. The weights may be negative, zero, or positive. The length of a path is the sum of the weights of the edges in the path. A path is simple if no vertex is repeated.

输出：寻找最权重简单的路径在一个给定的树

Output: finding the least weights simple path in a given tree.

推荐答案

下面是一个线性解的伪code：

Here is a pseudo code of a linear solution:

res = 0 // A path from a node to itself has a weight 0

// Runs depth first search from the v vertex and returns the weight of
// the shortest path that starts in a descendant of v and ends in v
def dfs(v):
    // The shortest path from a descendant of v to v
    minLength = 0
    // The list of all lengths of paths coming from children
    childLengths = []
    for edge in edges(v):
        childLength = dfs(edge.to)
        // Update the result with a vertical path from the child
        res = min(res, childLength + edge.weight) 
        // Update the minLength based on the child's value
        minLength = min(minLength, childLength + edge.weight)
        childLengths.add(childLength + edge.weight)
    if childLengths.size() >= 2:
        // Update the result based on two smallest children values.
        // Finds the the first and the second minimum in a list in a linear time.
        min1 = firstMin(childLengths)
        min2 = secondMin(childLengths)
        res = min(res, min1 + min2)
    return minLength    

dfs(root)
return res

如果树没有根，我们可以挑选任何一个顶点作为根。

If the tree is not rooted, we can pick any vertex as a root.