Algorithms / Bfs Shortest Path
Least You Need to Know: BFS Layers, Unweighted Shortest Paths, and Multi-Source Search
Breadth-first search works on **unweighted** graphs because it explores states in layers of equal edge distance. That layer structure is the interview reason BFS gives shortest-path lengths when every move costs the same.
The least you need to know
- BFS discovers nodes in nondecreasing number of edges from the source.
- The first time BFS reaches a node in an unweighted graph, that path length is shortest.
- Multi-source BFS starts several sources at distance 0 and grows one shared wavefront.
- Visited marking is usually done when enqueueing, not after dequeuing, to avoid duplicate work.
- Once edges have different positive weights, plain BFS no longer guarantees shortest weighted cost.
Key notation
dist(v)
shortest number of edges from the source set to node v
queue
FIFO structure that preserves layer order
multi-source BFS
BFS started from many distance-0 sources at once
Tiny worked example
- Suppose each word can change by one letter and each valid word is a node.
- Put the start word into a queue at distance 0.
- Every pop exposes all words one move farther away.
- Because BFS finishes distance 0 before distance 1, then distance 2, the first time you reach the target is the fewest moves.
Common mistakes
- Students often say BFS finds shortest paths even when edges have different weights.
- Students often mark visited too late and enqueue the same node many times.
- Students often miss that nearest-source problems are multi-source BFS, not many separate BFS runs.
How to recognize this kind of problem
- The prompt asks for the fewest moves, steps, hops, or transformations.
- Every legal move has the same cost.
- The state space can be explored in concentric distance layers.