Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Graphs

Shortest paths by breadth-first search

Lesson · 11 min read · Graphs · Pattern: shortest path by breadth-first search

When every move costs the same, the first time breadth-first search reaches a target is the shortest way there, whatever the "nodes" are.

What the pattern is

Breadth-first search reaches nodes in order of the number of steps from the start. If every step costs the same, that order is shortest-distance order, and the first time the search reaches the target it has found a shortest route. The pattern is about seeing that a problem is this one in disguise. The nodes may be cells, words, lock combinations or (position, keys held) pairs; the edges are the legal single moves.

Shortest path by breadth-first search

shortest(start, isGoal)

  1. Put every start state in the queue at distance 0 and mark it seen.
  2. Process the queue ring by ring. For each state, generate its neighbours: the states one move away.
  3. Mark a neighbour seen when it is queued. Return its distance as soon as it is a goal.
  4. If the queue empties, the goal cannot be reached.

Three variations

  • Multi-source. "Distance to the nearest exit from every cell", "minutes until every orange rots": put all sources in the queue at distance 0 at the start. One search, not one per source.
  • Implicit graph. In a word ladder each word is a node and its neighbours are the words one letter away. Generate neighbours on demand; never build the graph.
  • Extra state. If the rules depend on more than position (walls you may still break, keys you hold, direction you face), the node is the tuple. A grid with k wall removals left has rows × cols × (k + 1) states.

Multi-source search: both rotten oranges (value 2) spread at once; empty cells are walls.

  1. Step 1 / 3
    012301200

    All 2 source cells go into the queue together, at distance 0.

  2. Step 2 / 3
    012301201110

    Ring 1: 3 cells at distance 1, each one step from the previous ring. A cell is labelled by whichever source reaches it first, which is the nearest.

  3. Step 3 / 3
    012301201212210

    Ring 2: 3 cells at distance 2, each one step from the previous ring. A cell is labelled by whichever source reaches it first, which is the nearest.

the newest ringreached earlier

How to recognise it

  • "Minimum number of moves", "fewest steps", "shortest transformation", "how many minutes until".
  • Every move has the same cost. If moves have different costs, it is the Dijkstra pattern instead; if costs are only 0 or 1, a deque version (0-1 BFS) works.
  • The state space is finite and small enough to mark: count it before you write any code.
TimeO(states + transitions)
SpaceO(states)

For a grid with k removals: O(rows · cols · k). For a word ladder of n words of length L over 26 letters: O(n · L · 26).

The problems in this module: