Explain 'BFS' for shortest path.

Explain 'BFS' for shortest path.

Approach: Describe why BFS works for unweighted shortest paths.

BFS visits all nodes at distance k before any node at distance k+1. Thus, the first time a node is visited, it must be via the shortest possible path.

Follow-up: Does this work for weighted graphs?

Key concepts: levels, unweighted, queue.