Data Structures, Algorithms, & Applications in Java
Chapter 18, Exercise 33

To find the shortest path from the source vertex s to the vertex i, we first verify the existence of such a path. A path exists iff p[i] != 0. When the path exists, it may be constructed backwards from i to s by following the vertex sequence p[i], p[p[i]], p[p[p[i]]], ..., s.

The nethod AdjacencyWDigraph.path, which is given below, outputs the path backwards. If we must output the forward path, we can first store the backward path in an array and then output it in the desired order. A test program, input, and output appear in the files TestPath.*. 
/** output shortest path from vertex s to vertex i
  * @param p p[i] is predecessor of vertex i on shortest path */
public static void path(int [] p, int s, int i)
{
   if (p[i] == -1)
   {// no path from s to i
      System.out.println("There is no path from vertex "
           + s + " to vertex " + i);
      return;
   }

   // there is a shortest path to i
   // construct it backwards from i to s
   System.out.print("Shortest path from vertex "
        + s + " to vertex " + i + " is the reverse of " + i);
   while (i != s)
   {// move back one vertex
      i = p[i];
      System.out.print(" " + i);
   }
   System.out.println();
}


Since a shortest path has at most n vertices on it, the complexity of path is O(n).