Shortest Path in Unweighted Graph Using BFS in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS shortest path distances

What is the output of the following code that finds shortest path distances from node 0 in an unweighted graph?

DSA Python

from collections import deque

def bfs_shortest_path(graph, start):
    distances = {node: -1 for node in graph}
    distances[start] = 0
    queue = deque([start])
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    return distances

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

result = bfs_shortest_path(graph, 0)
print(result)

A {"0": 0, "1": 1, "2": 2, "3": 2, "4": 3}

B {"0": 0, "1": 1, "2": 1, "3": 1, "4": 2}

C {"0": 0, "1": 1, "2": 1, "3": 2, "4": 3}

D {"0": 0, "1": 0, "2": 1, "3": 2, "4": 3}

💡 Hint

Remember BFS explores neighbors level by level, so distances increase by 1 each step.

Starting from node 0, nodes 1 and 2 are at distance 1, node 3 is reached next at distance 2, and node 4 is at distance 3.

🧠 Conceptual

intermediate

Why BFS finds shortest path in unweighted graphs?

Why does BFS guarantee the shortest path in an unweighted graph?

A Because BFS explores nodes in increasing order of their distance from the start node.

B Because BFS uses a stack to explore nodes deeply first.

C Because BFS randomly visits nodes until it finds the target.

D Because BFS calculates edge weights during traversal.

💡 Hint

Think about how BFS visits nodes level by level.

BFS explores all nodes at distance d before nodes at distance d+1, so the first time it reaches a node, it is via the shortest path.

🔧 Debug

advanced

Identify the error in BFS shortest path code

What error does the following code produce when run on the given graph?

DSA Python

from collections import deque

def bfs_shortest_path(graph, start):
    distances = {node: None for node in graph}
    distances[start] = 0
    queue = deque([start])
    while queue:
        current = queue.pop()
        for neighbor in graph[current]:
            if distances[neighbor] is None:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    return distances

graph = {0: [2, 1], 1: [3], 2: [4], 3: [4], 4: []}
print(bfs_shortest_path(graph, 0))

A The code outputs incorrect distances because it uses pop() instead of popleft()

B The code raises an IndexError due to popping from an empty deque

C The code runs correctly and outputs {0: 0, 1: 1, 2: 2}

D The code raises a KeyError because of missing nodes in the graph

💡 Hint

Check how the queue is used to explore nodes.

Using pop() removes elements from the right end, making the queue behave like a stack (DFS), which can cause incorrect shortest path distances in BFS.

🚀 Application

advanced

Shortest path length in disconnected graph

Given this graph and start node 0, what is the shortest path distance to node 4?

DSA Python

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

# BFS shortest path distances from node 0
from collections import deque

def bfs_shortest_path(graph, start):
    distances = {node: -1 for node in graph}
    distances[start] = 0
    queue = deque([start])
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    return distances

result = bfs_shortest_path(graph, 0)
print(result[4])

A 0

B 3

C 2

D -1

💡 Hint

Check if node 4 is reachable from node 0.

Nodes 3 and 4 form a disconnected component from node 0, so distance remains -1 indicating unreachable.

🧠 Conceptual

expert

Why BFS is not suitable for weighted graphs?

Why does BFS fail to find the shortest path in graphs with weighted edges?

A Because BFS uses a stack instead of a queue.

B Because BFS treats all edges as having equal weight and does not consider actual weights.

C Because BFS cannot handle cycles in graphs.

D Because BFS only works on directed graphs.

💡 Hint

Think about how BFS measures distance in terms of edges.

BFS counts the number of edges, assuming each edge has equal cost. For weighted graphs, algorithms like Dijkstra consider edge weights to find true shortest paths.

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