Graph AlgosGraph Algorithms

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.

Learn BFS Shortest Path (Unweighted) →
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