Shortest Path in Unweighted Graph Using BFS in DSA Python - Deep Dive

Overview - Shortest Path in Unweighted Graph Using BFS

What is it?

The shortest path in an unweighted graph is the path between two points that uses the fewest edges. Breadth-First Search (BFS) is a method to explore all nodes layer by layer, starting from a source node. Using BFS, we can find the shortest path in terms of the number of edges between two nodes in a graph without weights. This method works because BFS explores neighbors in order of their distance from the start.

Why it matters

Finding the shortest path quickly is important in many real-life problems like navigation, social networks, and communication routing. Without BFS, finding the shortest path in unweighted graphs would be slower or more complex, making systems less efficient. For example, without this, GPS apps might take longer to find the fastest route, or messages in networks might take longer to reach their destination.

Where it fits

Before learning this, you should understand basic graph concepts like nodes, edges, and graph representations (adjacency lists or matrices). After mastering BFS for shortest paths, you can learn shortest paths in weighted graphs using algorithms like Dijkstra's or Bellman-Ford.

Mental Model

Core Idea

BFS finds the shortest path in an unweighted graph by exploring nodes in layers, ensuring the first time we reach a node is via the shortest route.

Think of it like...

Imagine standing in a room and calling out to your friends in the next rooms. You first reach friends in the closest rooms, then friends in rooms further away, layer by layer. The first time you hear from a friend, you know the shortest way to reach them.

Start (S)
  │
  ├─ Level 1 neighbors
  │    ├─ Level 2 neighbors
  │    │    ├─ Level 3 neighbors
  │    │    │    ...
  BFS explores nodes level by level, guaranteeing shortest path.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are made of nodes connected by edges; understanding this is key to BFS.

A graph is a collection of points called nodes (or vertices) connected by lines called edges. In an unweighted graph, edges have no cost or weight. For example, a social network where people are nodes and friendships are edges.

Result

You can visualize a graph as points connected by lines without any numbers on the lines.

Understanding the basic structure of graphs is essential before exploring how to find paths between nodes.

2

Foundation

What is Breadth-First Search (BFS)?

Concept: BFS explores nodes in layers starting from a source node.

BFS starts at a chosen node and explores all its neighbors first. Then it explores neighbors of neighbors, moving outward layer by layer. It uses a queue to keep track of nodes to visit next.

Result

Nodes are visited in order of their distance from the start node, ensuring closer nodes are visited first.

Knowing BFS explores nodes in layers helps us understand why it finds shortest paths in unweighted graphs.

3

Intermediate

Tracking Distance and Parents in BFS

🤔Before reading on: Do you think BFS alone can tell the exact shortest path, or just the distance? Commit to your answer.

Concept: To find the actual shortest path, BFS tracks distance and the parent node for each visited node.

During BFS, we keep two arrays or dictionaries: one for distance from the start node, and one for the parent node that led to the current node. This lets us reconstruct the path after BFS finishes.

Result

We get the shortest distance to each node and can trace back the path from any node to the start.

Tracking parents during BFS is crucial to not just know how far a node is, but also how to get there.

4

Intermediate

Implementing BFS for Shortest Path

🤔Before reading on: Will BFS find the shortest path if the graph has cycles? Commit to yes or no.

Concept: BFS can be implemented using a queue, distance, and parent tracking to find shortest paths even in graphs with cycles.

Initialize a queue with the start node. Mark its distance as 0 and parent as None. While the queue is not empty, dequeue a node, explore its neighbors. If a neighbor is unvisited, set its distance and parent, then enqueue it. Continue until all reachable nodes are visited.

Result

The BFS completes with distance and parent arrays filled, representing shortest paths from the start node.

Using a queue and marking visited nodes prevents infinite loops in cyclic graphs and ensures shortest paths.

5

Intermediate

Reconstructing the Shortest Path

🤔Before reading on: Do you think the shortest path is found by following parents from start to end or end to start? Commit to your answer.

Concept: The shortest path is reconstructed by following parent nodes backward from the destination to the start.

After BFS, to find the path from start to a target node, start at the target and repeatedly move to its parent until you reach the start node. Reverse this sequence to get the path from start to target.

Result

You get the exact sequence of nodes representing the shortest path.

Knowing to trace parents backward and then reverse the path is key to correctly reconstructing the shortest path.

6

Advanced

Handling Disconnected Graphs and No Path Cases

🤔Before reading on: If no path exists between two nodes, does BFS return an error or a special value? Commit to your answer.

Concept: BFS can detect unreachable nodes by checking if their distance remains unset after traversal.

If after BFS, the distance to a target node is still infinity or undefined, it means no path exists. The algorithm should handle this gracefully by reporting no path found.

Result

You can safely detect when no path exists and avoid incorrect path reconstruction.

Handling unreachable nodes prevents bugs and incorrect assumptions about connectivity.

7

Expert

Optimizing BFS with Early Stopping

🤔Before reading on: Can BFS stop early once the target node is found without losing correctness? Commit to yes or no.

Concept: BFS can stop as soon as the target node is dequeued, saving time in large graphs.

Since BFS explores nodes in order of distance, the first time the target node is dequeued, the shortest path is found. We can stop BFS immediately instead of exploring the whole graph.

Result

The algorithm runs faster by avoiding unnecessary exploration.

Early stopping leverages BFS's layer-by-layer nature to improve efficiency in practical applications.

Under the Hood

BFS uses a queue to explore nodes in order of their distance from the start. Each node is enqueued once when first discovered, ensuring the shortest path to it is recorded. The parent array stores the node from which we reached the current node, enabling path reconstruction. The distance array tracks how many edges away each node is from the start. This layer-by-layer exploration guarantees the shortest path in unweighted graphs.

Why designed this way?

BFS was designed to explore graphs systematically without revisiting nodes unnecessarily. Using a queue ensures nodes are processed in the order they are discovered, which naturally corresponds to increasing distance from the start. This design avoids complex bookkeeping and works efficiently for unweighted graphs, unlike depth-first search which can get lost deep in one branch.

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐       ┌─────────────┐
│ Queue       │──────▶│ Explore     │
│ (FIFO)      │       │ Neighbors   │
└──────┬──────┘       └──────┬──────┘
       │                     │
       ▼                     ▼
┌─────────────┐       ┌─────────────┐
│ Distance    │       │ Parent      │
│ Array       │       │ Array       │
└─────────────┘       └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does BFS always find the shortest path in weighted graphs? Commit to yes or no.

Common Belief: BFS finds the shortest path in any graph, weighted or unweighted.

Reality: BFS only guarantees shortest paths in unweighted graphs. For weighted graphs, BFS ignores weights and may find longer paths.

Why it matters: Using BFS on weighted graphs can lead to incorrect results, causing inefficient routes or wrong decisions.

Quick: If BFS visits a node twice, does it mean a shorter path was found? Commit to yes or no.

Common Belief: BFS can visit the same node multiple times to find shorter paths.

Reality: BFS visits each node only once when first discovered, ensuring the shortest path. Revisiting nodes is unnecessary and inefficient.

Why it matters: Revisiting nodes wastes time and can cause infinite loops if not handled properly.

Quick: Does BFS always find the shortest path even if the graph has cycles? Commit to yes or no.

Common Belief: Cycles in the graph prevent BFS from finding the shortest path.

Reality: BFS handles cycles correctly by marking visited nodes, so it still finds the shortest path.

Why it matters: Misunderstanding this can lead to avoiding BFS unnecessarily or implementing complex cycle detection.

Quick: Is the first path found by BFS always the shortest path? Commit to yes or no.

Common Belief: The first path BFS finds to a node might not be the shortest.

Reality: Because BFS explores nodes in order of distance, the first path found to any node is the shortest.

Why it matters: This property allows BFS to stop early when the target is found, improving efficiency.

Expert Zone

1

BFS's performance depends heavily on graph representation; adjacency lists are more efficient than adjacency matrices for sparse graphs.

2

In very large graphs, BFS can consume a lot of memory; techniques like bidirectional BFS can reduce search space.

3

Tracking parents for path reconstruction adds overhead but is essential for many applications; sometimes only distances are needed, allowing simpler BFS.

When NOT to use

BFS is not suitable for graphs with weighted edges where weights differ; use Dijkstra's or A* algorithms instead. Also, BFS is less efficient for very large or dense graphs without optimizations like bidirectional search.

Production Patterns

In real systems, BFS is used for shortest path in social networks, peer-to-peer networks, and routing in unweighted networks. Early stopping and parent tracking are standard. Bidirectional BFS is common to speed up searches between two nodes.

Connections

Dijkstra's Algorithm

Builds on BFS by adding weights to edges and using a priority queue.

Understanding BFS helps grasp Dijkstra's core idea of exploring nodes by shortest known distance, but with weights.

Queue Data Structure

BFS relies on queues to explore nodes in order of discovery.

Knowing how queues work clarifies why BFS visits nodes layer by layer, ensuring shortest paths.

Wave Propagation in Physics

BFS exploration mimics waves spreading out evenly from a source point.

Recognizing BFS as a wave helps understand why it finds shortest paths by expanding uniformly.

Common Pitfalls

#1 Not marking nodes as visited leads to infinite loops in cyclic graphs.

Wrong approach:

def bfs(graph, start):
queue = [start]
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
queue.append(neighbor) # No visited check

Correct approach:

def bfs(graph, start):
visited = set([start])
queue = [start]
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

Root cause:

Forgetting to track visited nodes causes repeated visits and infinite loops.

#2 Not tracking parents makes it impossible to reconstruct the shortest path.

Wrong approach:

def bfs(graph, start):
visited = set([start])
queue = [start]
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# No parent tracking

Correct approach:

def bfs(graph, start):
visited = set([start])
parent = {start: None}
queue = [start]
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node
queue.append(neighbor)

Root cause:

Ignoring parent tracking misses the path reconstruction step.

#3 Trying to use BFS for shortest path in weighted graphs leads to wrong results.

Wrong approach:

Use BFS directly on weighted graph edges without considering weights.

Correct approach:

Use Dijkstra's algorithm or A* for weighted graphs to find shortest paths correctly.

Root cause:

Misunderstanding BFS applicability to weighted graphs causes incorrect path calculations.

Key Takeaways

BFS explores nodes in layers, guaranteeing the shortest path in unweighted graphs.

Tracking distance and parent nodes during BFS allows exact shortest path reconstruction.

BFS handles cycles safely by marking visited nodes to avoid infinite loops.

Early stopping in BFS improves efficiency by ending search once the target is found.

BFS is not suitable for weighted graphs; specialized algorithms are needed there.

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