Data Structures, Algorithms, & Applications in Java
Chapter 17, Exercise 45

When the breadth first search is performed we label each vertex that s reached by both its distance (distance[]) from the source vertex s and the adjacenct vertex (nbr[]) used to reach the new vertex. The path is constructed after vertex d is reached by doing a traceback from vertex d to the source vertex using the nbr values. The code is given below. 
/** find a path from s to d by using breadth first search
  * @return the path in an array using positions 0 on up
  * @return null if there is no path */
public int [] findBFSPath(int s, int d)
{
   if (s == d)
   {// trivial path of length 0
      int [] path = new int [1];
      path[0] = s;
      return path;
   }

   // s != d, label vertices by distance until vertex d is labeled
   ArrayQueue q = new ArrayQueue(10);
                  // queue for breadth first search
   int [] nbr = new int [vertices() + 1];
                  // nbr[i] will be set to neighbor vertex from which
                  // vertex i is reached during the breadth first search
                  // by default nbr[i] = 0 initially
   int [] distance = new int [vertices() + 1];
                  // distance[i] will be set to distance from s to i

   q.put(new Integer(s));
   while (nbr[d] == 0 && !q.isEmpty())
   {// d has not been reached
      // remove a labeled vertex from the queue
      int w = ((Integer) q.remove()).intValue();

      // mark all unreached vertices adjacent from w
      Iterator iw = iterator(w);
      while (iw.hasNext())
      {// visit an adjacent vertex of w
         int u = ((EdgeNode) iw.next()).vertex; 
         if (nbr[u] == 0 && u != s)
         {// u is an unreached vertex
            q.put(new Integer(u));
            nbr[u] = w;
            distance[u] = distance[w] + 1;
         }
      }
   }

   if (nbr[d] == 0)
      // no path from s to d
      return null;

   // construct the path
   path = new int [distance[d] + 1];
   path[distance[d]] = d;
   for (int i = distance[d] - 1; i > 0; i--)
      path[i] = nbr[path[i + 1]];
   path[0] = s;

   return path;
}


A test program and sample input and output appear in the files TestFindBFSPath.*.

It is easy to see that the shortest path is found when s = d. So assume that s != d. The fact that the code actually finds the shortest path (i.e., the path with the fewest edges) follows from the following facts (1) if there is a path from s to vertex d, then nbr[d] and distance[d] get set to a nonzero value and (2) distance[i] is correctly set to the length of the shortest path from s to i (provided, of course, that distance[i] has a nonzero value upon termination).