Shortest Path in Unweighted Graph: BFS Distance Pattern

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.

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

Complexity

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