title: Returning only the vertices in the actual shortest path
body: <p>I know the title is a bit messy, but I don't know how to explain it better.</p>
  
  <p><strong>What I'm trying to do:</strong></p>
  
  <p>Using a graph found in a text file, find and print the shortest path (minimum amount of vertices) from vertex A to vertex B.</p>
  
  <p>Note: using breadth-first search, not Dijkstra's.</p>
  
  <p><strong>What I've got:</strong></p>
  
  <p>A working algorithm that applies BFS on the graph, but no good way of actually printing out the shortest path.</p>
  
  <p>I'm having a hard time <strong>distinguishing a vertex in the shortest path from one that is simply run through the algorithm, but not in the shortest path.</strong></p>
  
  <p>For example: Find the shortest path between 0 and 4.
  0 connects to 1,2 and 3. 1 connects to 4.
  My path turns out to be [0,1,2,3,4] instead of [0,1,4].</p>
  
  <p>I haven't been able to find any threads asking the same question, or any walk-through of BFS that includes this, so I'm not sure if I'm making this out to be <em>way</em> harder than it is?</p>
  
  <p><strong>Edit:</strong> code for those who may be interested (not sure at all if I'm avoiding circles?)</p>
  
  <p><strong>Edit 2:</strong> Changed the way I store my path to a Stack.</p>
  
  <pre><code>public String findPath(int v, int w) {
      Queue&lt;Integer&gt; q = new LinkedList&lt;Integer&gt;();
      boolean[] visited = new boolean[g.numVertices()];
  
      q.add(v);
      Stack&lt;Integer&gt; path = new Stack&lt;Integer&gt;();
      while(q.peek() != null) {
          runBFS(q.poll(),w,visited,q,path);
      }
      return path.toString();
  } 
  
  private void runBFS(int v, int w, boolean[] visited, Queue&lt;Integer&gt; q, Stack&lt;Integer&gt; path) {
      if(visited[v]) {
      }
      else if(v == w) {
          path.add(v);
          q.clear();
      }
      else {
          path.add(v);
          visited[v] = true;
          VertexIterator vi = g.adjacentVertices(v);
          while(vi.hasNext()) {
                  q.add(vi.next());
          }
      }
  }
  </code></pre>
  
  <p>Some explanation of variables and methods:</p>
  
  <p>v = vertex of origin</p>
  
  <p>w = target vertex</p>
  
  <p>g = graph</p>
  
  <p>vi = a normal iterator that iterates over the neighbours of v</p>
  
  <p><strong>Thanks for reading!</strong></p>