How Do You Find the Shortest Path in an Unweighted Graph?
Learn how to find the shortest path in an unweighted graph using BFS, with complexity and path reconstruction, for your interview.
Expected Interview Answer
The shortest path between two vertices in an unweighted graph is found with breadth-first search (BFS), which explores the graph level by level from the source and guarantees the first time a vertex is reached is via the fewest possible edges.
BFS uses a FIFO queue seeded with the source vertex, marks it visited, and repeatedly dequeues a vertex, enqueuing any unvisited neighbors while recording each one's distance as the current vertex's distance plus one and its predecessor for path reconstruction. Because BFS visits all vertices at distance k before any vertex at distance k+1, the first time it reaches the target vertex, that distance is guaranteed minimal — no algorithm needs to explore further once the target is dequeued. This runs in O(V + E) time and O(V) space, and the actual path is recovered by walking backward through the predecessor pointers from the target to the source. DFS cannot make this shortest-path guarantee because it commits to one branch before others, so it can reach the target via a much longer route first; BFS's queue-driven, layer-by-layer expansion is precisely what unweighted shortest path requires.
- O(V + E) time, no auxiliary priority queue needed unlike weighted shortest path
- Guarantees the fewest-edges path the first time the target is dequeued
- Simple predecessor-pointer trick reconstructs the actual path, not just its length
- Forms the basis for level-order traversal and connectivity checks too
AI Mentor Explanation
A scout wants to find the fewest number of introductions needed to connect a rookie bowler to a national selector through a chain of acquaintances. Starting from the rookie, the scout first checks every person the rookie directly knows, then everyone those people know, expanding outward one full ring of acquaintances at a time, never jumping ahead to check someone two rings away before finishing the current ring. The moment the selector appears in a ring, that ring number is guaranteed to be the fewest possible introductions, since every closer path would have surfaced the selector in an earlier ring already. This ring-by-ring expansion, using a simple waiting line of names to check next, is exactly how BFS guarantees the shortest unweighted path.
Step-by-Step Explanation
Step 1
Initialize the queue and distances
Enqueue the source, mark it visited with distance 0, all other distances unknown.
Step 2
Dequeue and expand neighbors
Pop the front vertex; for each unvisited neighbor, set distance = current + 1, record predecessor, enqueue it.
Step 3
Stop early on target found
The first time the target is dequeued (or discovered), its recorded distance is the guaranteed shortest path length.
Step 4
Reconstruct the path
Walk backward from the target through predecessor pointers to the source, then reverse the sequence.
What Interviewer Expects
- Name BFS specifically, not DFS, and explain why DFS cannot guarantee shortest path
- Describe the queue-based level-by-level expansion clearly
- State O(V + E) time and O(V) space complexity
- Explain how to reconstruct the actual path using predecessor pointers, not just the distance
Common Mistakes
- Using DFS and assuming it also finds the shortest path
- Forgetting to mark a vertex visited at enqueue time, causing duplicate processing
- Only computing the distance without tracking predecessors, unable to reconstruct the path
- Applying plain BFS to a weighted graph, where it does not guarantee shortest path (Dijkstra is needed instead)
Best Answer (HR Friendly)
“For an unweighted graph, I would use breadth-first search, exploring the graph in expanding rings from the starting point. Because it checks everything one edge away before anything two edges away, the very first time it reaches my target, I know that's the shortest possible path in terms of number of edges.”
Code Example
from collections import deque
def shortest_path(graph, source, target):
visited = {source}
queue = deque([source])
predecessor = {source: None}
while queue:
node = queue.popleft()
if node == target:
path = []
while node is not None:
path.append(node)
node = predecessor[node]
return path[::-1]
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
predecessor[neighbor] = node
queue.append(neighbor)
return None # target unreachableFollow-up Questions
- How would you adapt this to find the shortest path in a weighted graph?
- How would you find shortest paths from a source to all other vertices at once?
- What happens to BFS correctness if the graph has negative-weight edges?
- How would you find the shortest path between two vertices in a bidirectional search to speed things up?
MCQ Practice
1. Which algorithm guarantees the shortest path in an unweighted graph?
BFS explores vertices in strict order of increasing distance from the source, guaranteeing the first discovery of the target is via the shortest path.
2. What data structure does BFS use to control traversal order?
BFS uses a FIFO queue so vertices are processed in the order they were discovered, ensuring level-by-level expansion.
3. How is the actual shortest path (not just its length) reconstructed after running BFS?
Recording each vertex's predecessor during BFS lets you trace the path backward from target to source, then reverse it.
Flash Cards
Which traversal finds shortest path in an unweighted graph? — Breadth-first search (BFS).
What is the time complexity of BFS shortest path? — O(V + E), visiting every vertex and edge once.
Why can't DFS guarantee shortest path? — DFS commits to one branch fully before exploring others, so it can reach the target via a longer route first.
How do you recover the actual path after BFS, not just its length? — Track a predecessor for each vertex during traversal, then walk backward from the target to the source.