Znajdź najdłuższą ścieżkę od korzenia do liścia na drzewie

Mam drzewo (w sensie teorii grafów), takie jak następujący przykład:

Jest to ukierunkowane drzewo z jednym węzłem początkowym (korzeń) i wieloma końcowymi węzłami (liście). Każda krawędź ma przypisaną długość.

Moje pytanie brzmi: jak znaleźć najdłuższą ścieżkę, zaczynając od korzenia i kończąc na którymś z liści? Podejście brutalnej siły polega na sprawdzeniu wszystkich ścieżek liści korzenia i wybraniu ścieżki o maksymalnej długości, ale wolałbym bardziej wydajny algorytm, jeśli taki istnieje.

Ran G. dał wskazówki w kierunku wydajnego algorytmu, choć być może pominął pewne szczegóły. Obliczanie wszystkich ścieżek root-leaf jest rzeczywiście trochę nieefektywne, jeśli wykonujesz pracę w kółko, na przykład, jeśli obliczasz każdą ścieżkę, a następnie obliczasz długość.

Wykonaj następujący algorytm rekurencyjny, zaczynając od, a LongestPath(root)otrzymasz to, czego chcesz. Zasadniczo oblicza rekurencyjnie najdłuższą ścieżkę dla każdego poddrzewa. W każdym węźle wymaga to zbudowania nowych ścieżek i zwrócenia najdłuższej.

 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

Jest to kombinacja pseudokodu z pewną notacją Haskell, więc mam nadzieję, że jest zrozumiała.