BFS Shortest Path & Multi-Source BFS

When every step costs the same, the shortest path is the one with the fewest edges, and BFS finds it with no extra work. Multi-source BFS is the same loop with several starting points in the queue at once, which answers "how far is each cell from its nearest source?" in a single pass.

The idea#

BFS expands like a ripple: everything at distance 1, then everything at distance 2, and so on. A node at distance $d + 1$ can only be discovered from a node at distance $d$ , so the first time BFS reaches a node it has used the fewest possible edges. DFS has no such guarantee: it may reach the target first along a long, winding path.

The same guarantee carries over to many starting points. For several sources, put all of them in the queue at distance 0 before the loop starts. The layers then grow from every source together, and each cell is claimed by whichever source reaches it first, which is its nearest one. It behaves exactly like a single BFS from an imaginary super-source joined to every real source.

Why multi-source is O(mn)#

The payoff shows up in the cost. Say there are $g$ sources, such as the gates in Walls and Gates. Running a separate BFS from each of them costs $O(m \cdot n \cdot g)$ , which is $O((mn)^2)$ when most cells are gates. Seeding them all together needs one shared visited structure, so every cell is enqueued at most once across all the expansions. Finding the sources is $O(mn)$ , the BFS is $O(mn)$ , and the total is $O(mn)$ .

How to spot it#

The wording usually names the cost of a step, or makes clear that every step costs the same.

Cue	Meaning
"Shortest path", "fewest steps", "minimum moves", "nearest"	Single-source BFS
Every move costs exactly 1 (grid steps, swaps, rotations, hops between friends)	BFS, not Dijkstra
"Distance to the nearest X" for every cell, or "everything spreads at once"	Multi-source BFS
Moves change a state (a lock's digits, a board) rather than a position	BFS over implicit states
Steps have different costs	Not BFS: use Dijkstra

Template#

This version stores a distance grid, which doubles as the visited set (-1 means not reached yet). Pass one source for a normal BFS, or many for multi-source.

dist = grid of -1, same size as the input
queue = empty
for each source:
    dist[source] = 0                 # every source starts at 0
    push source onto queue
while queue is not empty:
    cell = pop from the front of queue
    for each neighbor of cell:
        if neighbor is off the grid or a wall: skip
        if dist[neighbor] != -1: skip   # a closer source got it
        dist[neighbor] = dist[cell] + 1 # mark on enqueue
        push neighbor onto queue
return dist

Carrying the distance inside the queue entry (cell plus distance) works as well. Either way, set the distance or mark visited when you enqueue, never when you pop.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Marking visited on pop, so the same cell enters the queue from several parents.
Running one BFS per source instead of seeding them all together.
Off-by-one on distance: decide whether you count cells or edges.
Forgetting to check whether the start itself is blocked.
Using BFS when edge weights differ; it then returns the fewest edges, not the lowest cost.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Shortest Path in Binary Matrix

Allow all 8 neighbors. The answer counts cells, not edges, so the start has distance 1. If the start cell is blocked, return -1 at once. A blocked end cell needs no special case, because it is never enqueued.

Hint: Rotting Oranges

Seed every rotten orange and count the fresh ones up front. When the BFS ends, compare the number infected with the fresh count; if some were never reached, return -1. The answer is the largest distance assigned, and 0 if there were no fresh oranges at all.

Hint: Walls and Gates

Seed every gate at distance 0 and write each room's distance straight into the grid. One pass gives every room its distance to the nearest gate.

Hint: Open the Lock

Each node is a 4-digit string. Each move turns one wheel up or down, so every state has 8 neighbors. The BFS loop is unchanged; only "get the neighbors" is different.

Hint: Find the Safest Path in a Grid

Two algorithms compose here. First run a multi-source BFS from every thief to build a "distance to nearest thief" grid. Then run a max-min path search over that grid, as in Bottleneck / Minimax Paths.

Hint: Word Ladder

Each word is a node and a one-letter change is an edge, so BFS finds the shortest sequence. Build neighbors through wildcard patterns like h*t mapped to their words, and remove a word from the set once you visit it.

Key takeaways#

In an unweighted graph, the first time BFS reaches a node is the shortest path.
Mark visited (or set the distance) when you enqueue.
Multi-source BFS seeds every source at distance 0 and costs $O(mn)$ , not $O(mn \cdot g)$ .
A distance grid initialized to -1 is both the answer and the visited set.
If steps cost different amounts, move on to Dijkstra.

Core idea#

When every step costs the same, BFS finds the shortest path. The first time BFS reaches a node, it has used the fewest edges. Multi-source BFS puts every source in the queue at distance 0.

Key points#

BFS expands in layers. A node at distance $d + 1$ comes only from a node at distance $d$ .
DFS has no shortest-path guarantee.
Multi-source BFS acts like one BFS from a super-source joined to every source.
Each cell is claimed by its nearest source.
One shared visited makes multi-source BFS $O(mn)$ , not $O(mn \cdot g)$ for g sources.
A distance grid set to -1 is both the answer and the visited set.
Set the distance or mark visited when you enqueue.
States work as nodes too. Open the Lock has 8 neighbor strings per state.

Spot it#

Cue	Use
Fewest steps, minimum moves, nearest	Single-source BFS
Every move costs exactly 1	BFS, not Dijkstra
Distance to the nearest X for every cell	Multi-source BFS
Steps have different costs	Dijkstra

Template#

dist = grid of -1; queue = empty
for each source:
    dist[source] = 0; push source onto queue
while queue is not empty:
    cell = pop from the front of queue
    for each neighbor of cell on the grid:
        if neighbor is open and dist[neighbor] == -1:
            dist[neighbor] = dist[cell] + 1   # mark on enqueue
            push neighbor onto queue
return dist

Pitfalls#

Marking visited on pop.
Running one BFS per source instead of seeding them all.
Off-by-one on distance. Binary Matrix counts cells, so the start is 1.
A blocked start cell. Return -1 at once.
Rotting Oranges: count fresh oranges first and return -1 if some stay unreached.

Say it in an interview#

"Unweighted, so BFS. The first visit is the shortest path."
"Seed every source at distance 0. One pass gives each cell its nearest source in O(mn)."