Shortest Path in Unweighted Graph Using BFS in DSA Python

Mental Model

We find the shortest path by exploring neighbors level by level, like ripples spreading out in water.

Analogy: Imagine you are in a city with streets connecting intersections. To find the shortest way to a destination, you check all intersections one step away first, then two steps away, and so on until you reach the target.

Graph:
0 -> 1 -> 2
↓    ↓
3    4

Start at 0, explore neighbors 1 and 3 first, then neighbors of 1 and 3, etc.

Dry Run Walkthrough

Input: Graph edges: 0-1, 0-3, 1-2, 1-4; Find shortest path from 0 to 4

Goal: Find the shortest path from node 0 to node 4 using BFS

Step 1: Start BFS from node 0, enqueue 0, distance[0] = 0

Queue: [0]
Distances: {0:0}
Path so far: none

Why: We begin from the start node with distance zero

Step 2: Dequeue 0, enqueue neighbors 1 and 3, set distance[1] = 1, distance[3] = 1, parent[1] = 0, parent[3] = 0

Queue: [1, 3]
Distances: {0:0, 1:1, 3:1}
Parents: {1:0, 3:0}

Why: Explore all nodes one step away from start

Step 3: Dequeue 1, enqueue neighbors 2 and 4, set distance[2] = 2, distance[4] = 2, parent[2] = 1, parent[4] = 1

Queue: [3, 2, 4]
Distances: {0:0, 1:1, 3:1, 2:2, 4:2}
Parents: {1:0, 3:0, 2:1, 4:1}

Why: Explore nodes two steps away; found target 4

Step 4: Target node 4 found, stop BFS

Queue: [3, 2, 4]
Distances: {0:0, 1:1, 3:1, 2:2, 4:2}
Parents: {1:0, 3:0, 2:1, 4:1}

Why: We found the shortest path to target

Step 5: Reconstruct path from 4 to 0 using parents: 4 -> 1 -> 0

Path: 0 -> 1 -> 4

Why: Trace back parents to get shortest path

Result:

Shortest path: 0 -> 1 -> 4

Annotated Code

DSA Python

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)  # undirected graph

    def bfs_shortest_path(self, start, target):
        queue = deque([start])
        distances = {start: 0}
        parents = {start: None}

        while queue:
            current = queue.popleft()
            if current == target:
                break
            for neighbor in self.adj[current]:
                if neighbor not in distances:
                    distances[neighbor] = distances[current] + 1
                    parents[neighbor] = current
                    queue.append(neighbor)

        if target not in distances:
            return None  # no path

        # Reconstruct path
        path = []
        node = target
        while node is not None:
            path.append(node)
            node = parents[node]
        path.reverse()
        return path


def main():
    g = Graph(5)
    g.add_edge(0, 1)
    g.add_edge(0, 3)
    g.add_edge(1, 2)
    g.add_edge(1, 4)

    start, target = 0, 4
    path = g.bfs_shortest_path(start, target)
    if path:
        print(' -> '.join(map(str, path)))
    else:
        print('No path found')

if __name__ == '__main__':
    main()

queue = deque([start])

Initialize queue with start node to begin BFS

distances = {start: 0}

Set distance of start node to zero

parents = {start: None}

Start node has no parent

current = queue.popleft()

Dequeue node to explore neighbors

if current == target: break

Stop BFS when target is found

for neighbor in self.adj[current]:

Check all neighbors of current node

if neighbor not in distances:

Visit unvisited neighbors only

distances[neighbor] = distances[current] + 1

Set distance for neighbor as one more than current

parents[neighbor] = current

Record parent to reconstruct path later

queue.append(neighbor)

Add neighbor to queue for further exploration

if target not in distances: return None

Return None if no path found

while node is not None: path.append(node); node = parents[node]

Trace back parents to build path from target to start

path.reverse()

Reverse path to get start to target order

Output

0 -> 1 -> 4

Complexity Analysis

Time: O(V + E) because BFS visits every vertex and edge once

Space: O(V) for storing distances, parents, and the queue

vs Alternative: Compared to DFS which may not find shortest path, BFS guarantees shortest path in unweighted graphs with similar time but more memory for queue

Edge Cases

No path exists between start and target

Function returns None and prints 'No path found'

DSA Python

if target not in distances: return None

Start equals target

Returns path with single node

DSA Python

queue = deque([start]) (handles immediate break if start == target)

Graph with isolated nodes

No path found if target isolated; returns None

DSA Python

if target not in distances: return None

When to Use This Pattern

When asked to find shortest path in an unweighted graph, use BFS because it explores nodes in layers ensuring the first time you reach the target is the shortest path.

Common Mistakes

Mistake: Not marking visited nodes causing infinite loops
Fix: Use a distances or visited set to track visited nodes before enqueueing

Mistake: Continuing BFS after finding target wasting time
Fix: Break BFS loop immediately when target is dequeued

Mistake: Not reconstructing path using parents, only returning distance
Fix: Store parents during BFS and trace back to build full path

Summary

Finds the shortest path between two nodes in an unweighted graph using BFS.

Use when you need the shortest route in a graph where edges have equal weight or no weight.

The key insight is BFS explores nodes in order of distance from start, so the first time you reach the target is the shortest path.

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The shortest path from a start node to all other nodes

B. The longest path in the graph

C. The node with the highest degree

D. The cycle in the graph

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of distance, it finds the shortest path to each node.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option A

4. Quick Check:

   BFS = Shortest path in unweighted graph [OK]

Hint: BFS explores neighbors level-wise to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS works only for weighted graphs

2. Which Python data structure is best to implement the queue needed for BFS?

easy

A. list with append() and pop(0)

B. collections.deque for efficient pops from front

C. set to store unique nodes

D. dictionary to map nodes to distances

Solution

1. Step 1: Identify queue operations in BFS

   BFS requires adding to the back and removing from the front efficiently.

2. Step 2: Choose data structure with O(1) pops from front

   collections.deque supports fast append and popleft operations, unlike list pop(0) which is slow.

3. Final Answer:

   collections.deque for efficient pops from front -> Option B

4. Quick Check:

   Use deque for BFS queue [OK]

Hint: Use deque for fast queue operations in BFS [OK]

Common Mistakes:

• Using list pop(0) causing slow performance
• Using set which is unordered
• Using dict which is not a queue

3. What is the output distance list after running BFS from node 0 on this graph?

graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}

medium

A. [0, 2, 2, 3]

B. [1, 0, 1, 2]

C. [0, 1, 1, 2]

D. [0, 1, 2, 3]

Solution

1. Step 1: Initialize distances and start BFS from node 0

   Distance to 0 is 0, others are infinity initially.

2. Step 2: Visit neighbors level-wise

   Neighbors of 0 are 1 and 2, distance 1 each. Then neighbor of 1 is 3, distance 2.

3. Final Answer:

   [0, 1, 1, 2] -> Option C

4. Quick Check:

   Distances = [0,1,1,2] [OK]

Hint: Distance increments by 1 per BFS level [OK]

Common Mistakes:

• Mixing node indices with distances
• Assigning wrong distances to neighbors
• Forgetting to update distances only once

4. Identify the bug in this BFS code snippet for shortest path:

def bfs(graph, start):
    from collections import deque
    queue = deque([start])
    distances = {start: 0}
    while queue:
        node = queue.pop()
        for neighbor in graph[node]:
            if neighbor not in distances:
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
    return distances

medium

A. Using queue.pop() instead of queue.popleft() causes wrong order

B. Distances dictionary should be a list

C. Neighbors should be checked before popping from queue

D. Start node distance should be -1

Solution

1. Step 1: Check queue operations in BFS

   BFS requires removing from front (FIFO), but pop() removes from end (LIFO).

2. Step 2: Identify correct method to remove front element

   queue.popleft() removes from front, preserving BFS order.

3. Final Answer:

   Using queue.pop() instead of queue.popleft() causes wrong order -> Option A

4. Quick Check:

   Use popleft() for BFS queue [OK]

Hint: Use popleft() to dequeue in BFS, not pop() [OK]

Common Mistakes:

• Using pop() causing DFS-like behavior
• Confusing list and dict for distances
• Incorrect initialization of distances

5. Given a grid where 0 represents open cell and 1 represents blocked cell, how can BFS be used to find the shortest path from top-left to bottom-right?

grid = [
  [0, 0, 1],
  [1, 0, 1],
  [1, 0, 0]
]

hard

A. Use BFS only on rows, ignoring columns

B. Run DFS to explore all paths and pick shortest

C. Use BFS but ignore blocked cells as neighbors

D. Treat each cell as a node, edges connect adjacent open cells; run BFS from start to find shortest path

Solution

1. Step 1: Model grid as graph nodes and edges

   Each open cell is a node; edges connect up/down/left/right neighbors if open.

2. Step 2: Run BFS from top-left to bottom-right

   BFS finds shortest path in unweighted graph; blocked cells are excluded from edges.

3. Final Answer:

   Treat each cell as a node, edges connect adjacent open cells; run BFS from start to find shortest path -> Option D

4. Quick Check:

   Grid BFS = shortest path via open neighbors [OK]

Hint: Model grid as graph, BFS finds shortest path avoiding blocks [OK]

Common Mistakes:

• Using DFS which is not shortest path
• Ignoring blocked cells incorrectly
• Not connecting neighbors properly