title: Shortest path using BFS in C++
body: <p>I have to write an algorithm to find the shortest path in an unweighted graph. I found out that the best way to find the shortest path in an unweighted graph is to simply perform a BFS and stop once the destination is reached. The problem is I don't know how to keep track of the path that led to that destination. </p>
  
  <p>So far I've thought about creating a new path list for every new node that is discovered, but I can't figure out how to implement that.</p>
  
  <p>This code seems to be working so far as visiting every node goes (it's a bit messy, sorry):</p>
  
  <pre><code>void shortestPath(string start, string finish, list&lt; list&lt;string&gt; &gt; adjList){
  
      queue&lt; list&lt; list&lt;vertex*&gt; &gt;::iterator &gt;    myQueue;
      list&lt; list&lt;vertex*&gt; &gt; listVertices = initializeVertices(start, adjList);
      list&lt; list&lt;vertex*&gt; &gt;::iterator aux = extractList(start, listVertices);
  
      myQueue.push(aux);
  
      while(myQueue.size() &gt; 0){
  
          list&lt; list&lt;vertex*&gt; &gt;::iterator vert = myQueue.front();
  
          for(list&lt;vertex*&gt;::iterator it = vert-&gt;begin(); it != vert-&gt;end(); it++){
              if((*it)-&gt;color == "white"){
                  (*it)-&gt;color = "gray";
                  myQueue.push(extractList((*it)-&gt;name, listVertices));
              }
  
          }
  
          list&lt;vertex*&gt;::iterator vertAux = vert-&gt;begin();
          (*vertAux)-&gt;color = "black";
          myQueue.pop();
      }
  }
  </code></pre>
  
  <p>Any ideas?</p>