Module 8 · Graphs and Trees · BFS on Graph

Shortest path in an undirected graph

With every edge of length 1, BFS finds shortest paths for free: it visits all vertices 1 edge away, then all 2 edges away, and so on. Processing the queue one level at a time, the level where the destination is polled is its distance.