Expanding distance layers
Starting at a source, breadth-first search examines vertices reachable by one edge, then two, then three. Layers count traversed edges. A vertex can have several incoming routes, but its first discovery places it in the earliest reachable layer.
A first-in, first-out queue stores discovered vertices whose adjacency lists remain to be examined. Removing one vertex exposes its unvisited neighbors, which are marked and enqueued. Processing continues until the queue empties or the required stopping condition is met.
References: [1]
Recording predecessors recovers a path
When a vertex is first discovered, a predecessor records which vertex reached it. Following predecessors backward and reversing the result reconstructs a minimum-edge path. Neighbor enumeration can determine which of several equally short alternatives is retained.
This guarantee concerns edge count, or a common unit cost per edge. Two expensive roads can cost more than three cheaper ones. Layered queue order does not by itself solve the general weighted shortest-path problem.
Marks and representation bound the work
Marking when enqueuing prevents different routes from repeatedly scheduling the same remaining work. Cycles therefore do not force endless expansion: each vertex in a finite graph needs to be expanded only once under the visited rule.
With adjacency lists, the traversal takes O(V+E) worst-case time for V vertices and E edges, with vertex-sized queue and bookkeeping space. Directed searches follow edge direction, and vertices unreachable from the source remain undiscovered.