title: How to find the shortest simple path in a Tree in a linear time?
body: <p>Here is a problem from Algorithms book by Vazirani</p>
  
  <blockquote>
    <p>The input to this problem is a tree T with integer weights on the edges. The weights may be negative,
    zero, or positive. Give a linear time algorithm to find the shortest simple path in T. The length of a
    path is the sum of the weights of the edges in the path. A path is simple if no vertex is repeated. Note
    that the endpoints of the path are unconstrained.</p>
    
    <p>HINT: This is very similar to the problem of finding the largest independent set in a tree.</p>
  </blockquote>
  
  <p>How can I solve this problem in linear time?</p>
  
  <p>Here is my algorithm but I'm wonder if it is linear time since it is nothing different than depth-first:</p>
  
  <blockquote>
    <ol>
    <li>Traverse tree (depth-first)</li>
    <li>Keep the indexes (nodes)</li>
    <li>add the values</li>
    <li>do (1) till the end of tree</li>
    <li>compare the sum and print the path and sum</li>
    </ol>
  </blockquote>
  
  <p>this problem is similar this <a href="https://stackoverflow.com/questions/2792865/how-to-minimize-total-cost-of-shortest-path-tree">topic</a> but there is no certain answer.</p>