3 deleted 1 characters in body
source | link

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 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'len

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 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'

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 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

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.

2 added 3 characters in body
source | link

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 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 (ppath,len) from previous step with largest value len'

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 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 (p,len) from previous step with largest value len'

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 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'

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.

1
source | link

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 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 (p,len) from previous step with largest value len'

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.