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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Binary Lifting, Power-of-Two Jumps, and Ancestor Queries.
Least You Need to Know: Binary Lifting, Power-of-Two Jumps, and Ancestor QueriesRelated lessons
Keep going with nearby lessons in the same topic.