title: Finding the shortest path nodes with breadth first search
body: <p><a href="https://i.stack.imgur.com/u0mFP.png" rel="noreferrer"><img src="https://i.stack.imgur.com/u0mFP.png" alt="enter image description here"></a></p>
  
  <p>I am running breadth first search on the above graph to find the shortest path from <code>Node 0</code> to <code>Node 6</code>. </p>
  
  <p>My code </p>
  
  <pre><code>public List&lt;Integer&gt; shortestPathBFS(int startNode, int nodeToBeFound){
          boolean shortestPathFound = false;
          Queue&lt;Integer&gt; queue = new LinkedList&lt;Integer&gt;();
          Set&lt;Integer&gt; visitedNodes = new HashSet&lt;Integer&gt;();
          List&lt;Integer&gt; shortestPath = new ArrayList&lt;Integer&gt;();
          queue.add(startNode);
          shortestPath.add(startNode);
  
          while (!queue.isEmpty()) {
              int nextNode = queue.peek();
              shortestPathFound = (nextNode == nodeToBeFound) ? true : false;
              if(shortestPathFound)break;
              visitedNodes.add(nextNode);
              System.out.println(queue);
              Integer unvisitedNode = this.getUnvisitedNode(nextNode, visitedNodes);
  
              if (unvisitedNode != null) {
                      queue.add(unvisitedNode);
                      visitedNodes.add(unvisitedNode);
                      shortestPath.add(nextNode); //Adding the previous node of the visited node 
                      shortestPathFound = (unvisitedNode == nodeToBeFound) ? true : false;
                      if(shortestPathFound)break;
                  } else {
                      queue.poll();
                  }
          }
          return shortestPath;
      }
  </code></pre>
  
  <p>I need to track down the nodes through which the BFS algo. traversed to reach node 6, like <code>[0,3,2,5,6]</code>. For that I have created a List named <code>shortestPath</code> &amp; trying to store the previous nodes of the visited nodes, to get the list of nodes. <a href="https://stackoverflow.com/a/18778681/1236153">Referred</a></p>
  
  <p>But it doesn't seem to work. The shortest path is <code>[0,3,2,5,6]</code></p>
  
  <p>In the list what I get is <code>Shortest path: [0, 0, 0, 0, 1, 3, 3, 2, 5]</code></p>
  
  <p>It's partially correct but gives the extra <code>1</code> .</p>
  
  <p>If I again start from the first element <code>0</code> of the <code>shortestPath</code> list &amp; start traversing &amp; backtracking. Like <code>1</code> doesn't has an edge to <code>3</code>, so I backtrack &amp; move from <code>0</code> to <code>3</code> to <code>5</code>, I will get the answer but not sure if that's the correct way.</p>
  
  <p>What is the ideal way to getting the nodes for the shortest path?</p>