title: A recursive DFS template to find the shortest path
body: <p>I am learning DFS through <a href="https://leetcode.com/explore/learn/card/queue-stack/232/practical-application-stack/1384/" rel="nofollow noreferrer">dfs-template I - LeetCode</a></p>
  
  <p>It introduced a recursion template </p>
  
  <pre><code>/*
   * Return true if there is a path from cur to target.
   */
  boolean DFS(Node cur, Node target, Set&lt;Node&gt; visited) {
      return true if cur is target;
      for (next : each neighbor of cur) {
          if (next is not in visited) {
              add next to visted;
              return true if DFS(next, target, visited) == true;
          }
      }
      return false;
  }
  </code></pre>
  
  <p>A question raised in the end</p>
  
  <blockquote>
    <p>In the template above, we stop when we find the <code>first</code> path.</p>
    
    <p>What if you want to find the <code>shortest</code> path?</p>
    
    <p>Hint: Add one more parameter to indicate the shortest path you have already found.</p>
  </blockquote>
  
  <p>How to find the shortest path?</p>
  
  <p>I assumed that a <code>step</code> parameter should be added to remember  <code>depth</code> of  each turn to traverse, after exhausted all all the possible paths, compare the depths and return the minimal.</p>
  
  <p>Where is the parameter <code>step</code>  placed?</p>