Graph Theory37 sections · 1633 units
Open in Course

Why does this find Shortest Path?

The Logic

BFS guarantees the first path to a node is the shortest. Here is why. Suppose the shortest path to node vv has length 33. BFS processes nodes at distance 00 first, then distance 11, then distance 22, then distance 33. When BFS reaches distance 33, it visits vv. All nodes at distance 00, 11, and 22 are already visited.

So the path to vv must go through nodes at those distances. Since BFS processes nodes in order of increasing distance, the first time you reach vv must be via the shortest path. There is no shorter path hiding somewhere else.