Найдите самый длинный путь от корня до листа на дереве

У меня есть дерево (в смысле теории графов), например, в следующем примере:

Это направленное дерево с одним начальным узлом (корень) и множеством конечных узлов (листья). Каждому ребру назначена длина.

Мой вопрос: как найти самый длинный путь, начинающийся у корня и заканчивающийся у любого из листьев? Подход грубой силы состоит в том, чтобы проверить все пути корневых листьев и выбрать путь с максимальной длиной, но я бы предпочел более эффективный алгоритм, если он есть.

Ран Г. дал намеки на эффективный алгоритм, хотя, возможно, он не учел некоторые детали. Вычисление всех корневых путей действительно немного неэффективно, если вы выполняете работу снова и снова, например, если вы вычисляете каждый путь, а затем вычисляете длину.

Выполните следующий рекурсивный алгоритм, начиная с 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, поэтому я надеюсь, что она понятна.