查找树中简单路径的最小权重

Question

我运行遇到了一个问题，我们想设计一个高效的算法来寻找一条权重最轻的简单路径。（具有最小权重的简单路径）。

我认为这不是多项式解，但有些朋友说可能是 O(n) 或 O(n^2) 或 O(n lg n) 会是... !

程序员或高手，能帮帮我吗？任何伪代码？

编辑：

这个问题的输入是一棵边上有整数权重的树T。权重可以是负数、零或正数。路径的长度是路径中边的权重之和。如果没有重复的顶点，则路径是简单的。

输出：找到给定树中权重最小的简单路径。

Answer 1

在一棵树中，每对节点之间只有一条简单路径 (there's a proof here)。

因此，即使您尝试每对节点找到它们之间的路径，您也会有一个 O(n^3) 算法。

一个更好的方法是为每个节点找到单次访问中每个其他节点的成本。这将算法降低到 O(n^2).

Answer 2

有一个简单的 O(n) 算法，它基于这样一个事实：在树中总会有一些叶子，如果我们删除一个叶子，剩下的图仍然是树。所以我们可以一个一个的删除叶子，这样处理所有的树（所有的边）。

您需要为每个节点保留找到的最轻路径。

因此，假设您正在处理一些叶子节点 n 是节点叶子节点所连接的，并且我们希望确保您关注通过连接此 n 和叶子节点的边缘的任何路径。来看图

这里的方向只是指从早先删除的节点到他们"parents"后面要删除的节点的方向，它可能取决于你正在处理的订单n离开。

如果我们有通过叶子和 n 的最短路径，它可以将叶子的任何 "child" 与 n 的其他子节点连接起来，或者它可以将叶子的任何 "child" 连接到其余部分树的。

在这两种情况下，保持从任何已处理节点到当前节点的最短路径就足够了。当我们处理叶子时，我们采用为叶子建立的最轻路径并向其添加连接权重并将其与已为 n 保存的最短路径进行比较。以这种方式，我们不可避免地会比较 n 的两条最短路径，并且能够将它们联合起来，并且当 n 的所有 "children" 都被处理时，将保存 n 的最短路径。

所以这是伪代码。

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);
     }
}

所以在主循环中我们只处理了每个节点一次所以我们有 O(n) 的复杂度。如果您需要非零长度路径但该算法没有找到它，则意味着所有边都具有正权重并且最轻的非零长度路径是最轻的边。

Answer 3

下面是一个线性解的伪代码：

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

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

查找树中简单路径的最小权重

Find Minimum Weight of Simple Path in Tree

algorithm

tree

graph

shortest-path

data-structures