在树上找到从根到叶的最长路径

Question

我有一个 树 （从图理论意义上），例如以下示例：

这是一个有向树，有一个起始节点（根）和许多结尾节点（叶子）。每个边缘都有一个分配的长度。

我的问题是，如何找到从根部开始并以任何叶子结束的最长路径？蛮力的方法是检查所有根叶路径，并以最大长度的速度采用该路径，但是如果有的话，我更喜欢更有效的算法。

Answer 1

Ran G.给出了有效算法的提示，尽管也许他遗漏了一些细节。如果您一遍又一遍地进行工作，则计算所有根叶路径的确有点降低，例如，如果您计算每个路径然后计算长度。

从开始执行以下递归算法 LongestPath(root) 会给你想要的。本质上，它递归计算每个子树的最长路径。在每个节点上，这都需要构建新路径并返回最长的路径。

 LongestPath(node)
   If node is a leaf, return (node,0) 
   If node is not a leaf:  
    For each edge (node,length,next):
       Let (p,l) = LongestPath(next)
       Let (path,len) = (p++[next], l + length)
    Return element (path,len) from previous step with largest value len

如果使用一些Haskell表示法，则这是一个组合，因此我希望它可以理解。