Shortest Path in Unweighted Graph DSA Solution

Learning Outcome

After this lesson, you should be able to use BFS levels as distance in an unweighted graph.

Problem Statement

Given n nodes, undirected edges, a source, and a destination, return the shortest number of edges from source to destination.

Input	Output	Why
`n = 5, edges = [[0,1],[1,2],[0,3],[3,4]], src = 0, dst = 4`	`2`	The shortest path is 0 to 3 to 4.

Brute Force Approach

Use DFS to enumerate all paths and then choose the shortest. DFS may explore long paths before short paths.

Optimized Approach

Build an adjacency list and run BFS from the source. The first time a node is reached, its distance is shortest.

Exact Pseudocode

build adjacency list
queue = [(source, 0)]
mark source as seen
while queue not empty:
  node, distance = pop front
  if node is destination:
    return distance
  for neighbor in adj[node]:
    if neighbor is unseen:
      mark neighbor as seen
      push (neighbor, distance + 1)
return -1

Reference Code

from collections import deque

class Solution:
    def shortestPath(self, n, edges, src, dst):
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        q = deque([(src, 0)])
        seen = {src}

        while q:
            node, dist = q.popleft()
            if node == dst:
                return dist
            for nei in adj[node]:
                if nei not in seen:
                    seen.add(nei)
                    q.append((nei, dist + 1))
        return -1

Sample Dry Run

Step	State	Result
Start	queue = [(0,0)]	seen = {0}
Pop 0	Add 1 and 3 with distance 1	queue = [(1,1),(3,1)]
Pop 3	Add 4 with distance 2	queue includes destination
Pop 4	Destination reached	return 2

Complexity

Measure	Value	Reason
Time	O(n + e)	BFS processes each node and edge at most once.
Space	O(n + e)	Adjacency, queue, and seen set take linear space.

Edge Cases

If source equals destination, return 0.
If destination is unreachable, return -1.
This works for unweighted graphs, not weighted shortest path.

Interview Checklist

Mark nodes when enqueued, not when popped.
Store distance with each node or level by level.
Return as soon as destination is popped or first reached.

FAQs

Why does BFS give shortest distance?

BFS explores all nodes at distance d before any node at distance d + 1.

Can DFS solve this?

DFS can find a path, but it does not naturally guarantee the shortest unweighted path.

What is the core pattern?

BFS layer distance.

Shortest Path in Unweighted Graph: BFS Distance Pattern