Shortest Paths in an Unweighted Graph

Think about which traversal order visits vertices in increasing order of distance from the source.

This traversal explores all vertices at distance k before any vertex at distance k+1.

1. 1. Identify the traversal order

   Breadth-first search explores vertices level by level outward from the source, visiting all vertices at distance $k$ before any at distance $k+1$.

2. 2. Conclude correctness

   Since every edge has the same unit weight, this level-order visiting order exactly matches shortest-path distance, so the first time a vertex is reached gives its shortest distance.

Answer: Breadth-first search.