title: Depth First Search to find shortest path?
body: <p>I know this is usually done with breadth first, but we are asked to do it with both, I already accomplished breadth first....</p>
  
  <p>I feel like this is a pretty typical example of using a depth first search, so I was hoping I could get some help here...  I am attempting to find the shortest path through a maze using depth first search, but as of right now I cannot wrap my head around how exactly to do it.  This is my code so far:</p>
  
  <pre><code>void maze::findPathRecursive(graph &amp;g, int position, int goal) {
      if (position == goal) {
          isPath = true; //returns true if there is a path to the goal
          correctPath.push_back(position); // the path to the goal
      } else {
          g.mark(position);
          g.visit(position);
  
          //gets all the neighbors of the current position
          vector&lt;int&gt; neighbors = getNeighbors(position, g);
  
          while (!neighbors.empty()) {
              int n = neighbors.back();
              neighbors.pop_back();
  
              if (!g.isVisited(n)) {
                  findPathRecursive(g, n, goal);
              } 
  
              if (isPath) {
                  correctPath.push_back(position);
                  break;
              } 
          } 
      } 
  } 
  </code></pre>
  
  <p>Right now, what this does is find the first path it can to the goal and breaks from there.  I know I'll need to get rid of the break and I tried making another vector to store the shortest path and compare the lengths between it and the previous shortest but it did not work because I feel like I need to unvisit nodes at some point but cannot figure out how exactly to do it here.  </p>
  
  <p>Any help is greatly appreciated!!</p>
  
  <p>g is a graph by the way which contains the maze.  </p>