title: How to find a graph augmenting path
body: <p>I'm trying to implement the <strong>Ford-Fulkerson algorithm</strong> to compute the maximum flow in a flow network. </p>
  
  <p>One step of the algorithm is to <strong>find a path</strong> from the start node to the end node (also know as <em>sink</em>) with available capacity on all edges.</p>
  
  <p>Could you suggest a easy and understandable way to find the <strong>augmenting path</strong>?</p>
  
  <p><strong>UPDATE #1:</strong></p>
  
  <p>My BFS function:</p>
  
  <pre><code>template &lt;class T&gt;
  vector&lt;Vertex&lt;T&gt; *&gt; Graph&lt;T&gt;::bfs(T source) const {
      vector&lt;Vertex&lt;T&gt; *&gt; path;
      queue&lt;Vertex&lt;T&gt; *&gt; q;
      Vertex&lt;T&gt; * v = getVertex(source);
      q.push(v);
      v-&gt;visited = true;
      while (!q.empty()) {
          Vertex&lt;T&gt; *v1 = q.front();
          q.pop();
          path.push_back(v1);
          typename vector&lt;Edge&lt;T&gt; &gt;::iterator it = v1-&gt;adj.begin();
          typename vector&lt;Edge&lt;T&gt; &gt;::iterator ite = v1-&gt;adj.end();
          for (; it!=ite; it++) {
              Vertex&lt;T&gt; *d = it-&gt;dest;
              if (d-&gt;visited == false) {
                  d-&gt;visited = true;
                  q.push(d);
              }
          }
      }
  
      return path;
  }
  </code></pre>
  
  <p>It's wrong/incomplete since it's returning wrong results. I think I'm forgeting something.</p>