问求树中简单路径的最小权

EN

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

for each (node in graph)
{
   node.shortest_path = 0; //zero length path from this node to this node
}
leaves = new list(all leaves in graph); //O(n) to find
int minWeight = 0; //any zero length path is minimum weight path currently found

//note that we a going to add new elements in list during the iteration
//and we will need to iterate through all of them including new added
//so in usual programming languages you will need to use for cycle
for each (leaf in leaves)
{
       //we will have last node in tree with no connection
       //because we will delete it on previous iteration
       //and we don't need to process this node
       //for this problem it is last node, 
       //but it may be not last if we have several trees instead of one
       if (no point connected to leaf) continue; 

     n = only one node still connected to leaf       
     connection = connection between n and leaf

     //check if we can make a short path which goes through n 
     //from one already processed "child" node to another
     if (leaf.shortest_path + 
         connection.weight 
         + n.shortest_path < minWeight  )
     {
         minWeight = leaf.shortest_path+connection.weight+n.shortest_path; 
     }
     //and we need to keep lightest path from any processed "child" to n
     if (leaf.shortest_path + connection.weight < n.shortest_path )
     {
          n.shortest_path = leaf.shortest_path + connection.weight;
          if(n.shortest_path < minWeight )
          {
               minWeight = n.shortest_path;
          }
     }

     //delete connection and 
     connection.delete();
     //if n is now leaf add it to leaf list
     if (n is leaf) 
     {
         leaves.Add(n);
     }
}