Breadth First Search

BFS(graph G, vertex s)
[all nodes initially unexplored]
-mark s as explored
let Q = queue data structure, initialized with s
while (Q not empty)
     remove the first node of Q, call it v
     for each edge (v, w):
          if w is unexplored
               mark w as explored
               add w to Q (at the end)

Layer n+1 gets added to the queue when we process layer n. We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we're at node v and at node w).

Using breadth first search, we can implement a shortest path algorithm quite easily. The goal is to compute dist(v), the fewest number of edges on a path from s to v.

The only extra code we need to incorporate is:
initialize dist(v) = {0 if v=s, infinity if v != s}. When considering edge (v, w), if w is unexplored, then set dist(w) = dist(v)+1.