Graph AlgosAlgorithmaka unweighted shortest path, fewest edges path

BFS Shortest Path (Unweighted)

Shortest path in an unweighted graph: BFS from the source, record parents, then walk parents back from the target to reconstruct the path.

▶ VisualizePattern: Breadth-First SearchPractice (4)
Progress

Overview

When every edge costs the same, the shortest path is the one with the fewest edges, and Breadth-First Search (BFS) computes it exactly: the first time BFS reaches a node is along a minimum-hop path. Storing parent[v] at discovery time lets you rebuild the actual path by walking from the target back to the source and reversing.

Preconditions: unweighted (or all weights equal) edges, directed or undirected. Complexity O(V + E) — no heap, no log factor. This is the cheapest shortest-path algorithm there is, so always ask "are the edges really weighted?" before reaching for Dijkstra's Algorithm.

shortest pathunweightedpath reconstructionO(V + E)

Intuition

A mental model before the formal terms.

Imagine everyone in a social network forwarding a message to all their friends once per day. The day a person first receives it is their distance from the origin, and the friend they heard it from first is their parent. To find how the message reached you, ask "who told you?" repeatedly until you reach the sender — that chain is a shortest path.

How it works

  1. Run BFS from s with dist[s] = 0, parent[s] = -1. When discovering v from u, set dist[v] = dist[u] + 1, parent[v] = u.
  2. Optionally stop as soon as t is dequeued (or even enqueued) — every node still in the queue is at distance ≥ dist[t].
  3. If t was never reached, there is no path. Otherwise, start at t and follow parent pointers until -1, collecting nodes; reverse to get s → … → t.
  4. For grids, "nodes" are cells and "edges" are the 4 (or 8) neighbour moves; the adjacency list is generated on the fly from a delta array.

Why it works

BFS dequeues nodes in non-decreasing distance order, so parent[v] is a node at distance dist[v] - 1. Following parents therefore decreases distance by exactly 1 per step and reaches s after dist[t] steps: the reconstructed path has length dist[t].

No shorter path can exist: any path of length k from s to t would have put t in level ≤ k, and BFS records the minimal level.

Recognition

How to tell a problem wants this.

  • "Minimum number of moves/steps/transformations" where each move has the same cost.
  • Grid with obstacles: "shortest path from top-left to bottom-right".
  • Implicit graphs: word ladder, knight moves, sliding puzzle, lock combinations.
  • The problem asks for the path itself, not just its length — you need parent.
“minimum steps” → Breadth-First Search

Interactive visualization

Play, step, change the input. ← → and space work too.

A0BCDEFGHIJKL
Queue (front → back)
A
1/30Find the fewest-edge path from A to L. BFS visits nodes in order of distance, so the first time we reach L its parent chain is a shortest path.
SourceTargetCurrent nodeIn queueVisitedShortest path
PseudocodeLearn BFS Shortest Path (Unweighted) →
1queue = [source]; parent = {source: None}
2while queue not empty:
3  u = queue.popleft()
4  if u == target: break
5  for v in neighbors(u):
6    if v not in parent:
7      parent[v] = u; queue.append(v)
8path = follow parent from target back to source, reversed
Complexity
best O(1)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1dist[s] = 0; parent[s] = -1; queue = [s]
2while queue not empty:
3  u = queue.popleft(); if u == t: break
4  for v in adj[u]:
5    if dist[v] undefined: dist[v] = dist[u] + 1; parent[v] = u; queue.append(v)
6if dist[t] undefined: return none
7path = []; cur = t; while cur != -1: path.append(cur); cur = parent[cur]
8return reversed(path)

Implementations

1from collections import deque
2 
3 
4def bfs_shortest_path(adj: list[list[int]], s: int, t: int) -> list[int] | None:
5    """Fewest-edges path from s to t, or None if unreachable. Nodes are 0..n-1."""
61 · Initialize parents and queue
7    n = len(adj)
8    parent = [-1] * n
9    seen = [False] * n
10    seen[s] = True
11    q = deque([s])
122 · BFS with early exit
13    while q:
14        u = q.popleft()
15        if u == t:
16            break
173 · Discover neighbours
18        for v in adj[u]:
19            if not seen[v]:
20                seen[v] = True
21                parent[v] = u
22                q.append(v)
234 · Reconstruct path
24    if not seen[t]:
25        return None
26    path = []
27    cur = t
28    while cur != -1:
29        path.append(cur)
30        cur = parent[cur]
31    path.reverse()
32    return path
Walkthrough
  1. deque for O(1) popleft().
  2. break as soon as t is popped; seen[t] tells afterwards whether it was ever discovered.
  3. None signals unreachable; list[int] | None is the Python 3.10+ union syntax.
  4. The parent walk appends nodes from t back to s, then path.reverse() fixes the order in place.
Complexity (this implementation)
time O(V + E) · space O(V)
Language notes
  • path[::-1] would also work but creates a copy; list.reverse() is in place.
  • Type hint list[int] | None requires Python 3.10; use Optional[list[int]] before that.
  • For grid problems, generate neighbours on the fly from a delta list instead of materialising adj.
Common mistakes in this language
  • Using list.pop(0).
  • Testing if not path: to detect unreachable when the path could legitimately be empty — return None and test is None.
  • Forgetting to mark s seen before the loop, so it can be re-enqueued through a cycle.
Language differences that matter here
  • Unreachable sentinel: C++ returns an empty vector, JS/TS return null, Python returns None. The typed languages (TS strict mode) force the caller to handle it.
  • Reversal: C++ std::reverse(begin, end), JS/TS Array.prototype.reverse() (in place), Python list.reverse() (in place) or [::-1] (copy).
  • Queue: only JS/TS lack a built-in O(1) deque, hence the head index.

Complexity

Best
O(1)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Best case: target is the source or an immediate neighbour and the search stops early. Path reconstruction is O(path length) ≤ O(V).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • All edges have equal weight — this beats Dijkstra by a log factor and is simpler.
  • Grid mazes, puzzles, and word-transformation problems (implicit unweighted graphs).
  • You need distances from one source to all nodes in a single pass.
  • The graph is huge but the target is expected to be close: early exit keeps the explored region small.
Avoid it when

Alternatives

Dijkstra's Algorithm0-1 BFSBellman-FordA* Search
Compare: BFS vs Dijkstra

Common mistakes

  • Reconstructing the path from s forward instead of from t backward — parents only point toward the source.
  • Checking u == t only at dequeue but also updating dist for nodes already visited, corrupting distances.
  • Breaking on discovery of t but then reading dist[t] from an uninitialised entry because it was set after the check.
  • On grids, forgetting that the start cell may itself be blocked, or that the answer counts cells rather than edges (off by one).
  • Bidirectional BFS bookkeeping errors: the meeting node must be checked when expanding, and the smaller frontier should be expanded first.

Interview patterns

  • Shortest path in binary matrix with 8-directional moves.
  • Word ladder: BFS over words; generate neighbours by substituting each position with a–z, O(L · 26) per word.
  • Bidirectional BFS to cut the explored region from b^d to roughly 2·b^(d/2).
  • State-augmented BFS: node = (cell, keys collected) or (cell, obstacles removed so far) when a small extra dimension changes reachability.
  • Multi-source BFS for "distance to nearest 0" (01 matrix).
Interview questions on this
Mock interviews

Example problems

Binary Tree Level Order TraversalmediumWord LadderhardShortest Path in Binary MatrixmediumRotting Orangesmedium