Trouvez le chemin le plus long de la racine à la feuille dans un arbre

J'ai un arbre (au sens de la théorie des graphes), tel que l'exemple suivant:

Il s'agit d'un arbre dirigé avec un nœud de départ (la racine) et plusieurs nœuds de fin (les feuilles). Chacune des arêtes a une longueur qui lui est affectée.

Ma question est, comment trouver le chemin le plus long commençant à la racine et se terminant à l'une des feuilles? L'approche par force brute consiste à vérifier tous les chemins racine-feuille et à prendre celui de longueur maximale, mais je préférerais un algorithme plus efficace s'il en existe un.

Ran G. a donné des indices sur un algorithme efficace, bien qu'il ait peut-être omis certains détails. Calculer tous les chemins racine-feuille est en effet un peu inefficace si vous travaillez encore et encore, par exemple, si vous calculez chaque chemin puis calculez la longueur.

Effectuer l'algorithme récursif suivant en commençant par LongestPath(root)donnera ce que vous voulez. Essentiellement, il calcule récursivement le chemin le plus long pour chaque sous-arbre. À chaque nœud, cela nécessite de créer les nouveaux chemins et de renvoyer le plus long.

 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

Il s'agit d'une combinaison de pseudo-code avec une notation Haskell, donc j'espère que c'est compréhensible.